正文 

当前位置： 首页 > java > java教程

bzoj1827:[usaco2010mar]gather奶牛大集会

ONION_CYC ONION_CYC     2022-09-17     639

关键词：

【算法】树型DP

【题解】

两遍DFS，第一次得到所有节点子树的路径和，第二次给出除了该子树外其它部分的路径和，时时计算答案。

long long！！！

技术分享 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define ll long long
using namespace std;
const int maxn=100010;
struct edge{int v,w,from;}e[maxn*2];//边数组开大！ 
int first[maxn],tot,size[maxn],n,a[maxn],N;
ll f[maxn],g[maxn],ans;

int read()
{
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c==‘-‘)t=-1;
    do{s=s*10+c-‘0‘;}while(isdigit(c=getchar()));
    return s*t;
}
void insert(int u,int v,int w)
{tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}
void dfs1(int x,int fa){
    f[x]=0;size[x]=a[x];
    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
        dfs1(e[i].v,x);
        size[x]+=size[e[i].v];
        g[e[i].v]=f[e[i].v]+1ll*size[e[i].v]*e[i].w;
        f[x]+=g[e[i].v];
    }
}
void dfs2(int x,int fa,ll num){
    ans=min(ans,num+f[x]);
    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
        dfs2(e[i].v,x,num+f[x]-g[e[i].v]+1ll*(N-size[e[i].v])*e[i].w);
    }
}
    
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)a[i]=read(),N+=a[i];
    int u,v,w;
    for(int i=1;i<n;i++){
        u=read();v=read();w=read();
        insert(u,v,w);insert(v,u,w);
    }
    dfs1(1,-1);
    ans=(1ll<<60);
    dfs2(1,-1,0);
    printf("%lld",ans);
    return 0;
}
View Code

 

嘴巴题4「bzoj1827」[usaco2010mar]gather奶牛大集会

1827:[Usaco2010Mar]gather奶牛大集会DescriptionBessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农... 查看详情

bzoj1827[usaco2010mar]gather奶牛大集会（树形dp）

 【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1827 【题目大意】　　给出一棵有点权和边权的树，　　请确定一个点，使得每个点到这个点的距离乘上该点乘积的总和最小。 【题解】　　定1为根，我们先计... 查看详情

bzoj1827[usaco2010mar]gather奶牛大集会

题目描述 Description Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路... 查看详情

bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)

【题解】　　很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。　　我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。　　显然选择它的儿子... 查看详情

bzoj_1828_[usaco2010mar]balloc农场分配_线段树

BZOJ_1828_[Usaco2010Mar]balloc农场分配_线段树DescriptionInput第1行：两个用空格隔开的整数：N和M*第2行到N+1行：第i+1行表示一个整数C_i*第N+2到N+M+1行：第i+N+1行表示2个整数A_i和B_iOutput*第一行：一个整数表示最多能够被满足的要求数SampleI... 查看详情

[bzoj1637][usaco2007mar]balancedlineup

1637:[Usaco2007Mar]BalancedLineupTimeLimit:5Sec  MemoryLimit:64MBSubmit:693  Solved:460[Submit][Status][Discuss]DescriptionFarmerJohn决定给他的奶牛们照一张合影，他让N(1≤N≤50,000)头奶牛站成一条直线，每头牛都有它的坐 查看详情

bzoj1637:[usaco2007mar]balancedlineup

1637:[Usaco2007Mar]BalancedLineupTimeLimit: 5Sec  MemoryLimit: 64MBDescriptionFarmerJohn决定给他的奶牛们照一张合影，他让N(1≤N≤50,000)头奶牛站成一条直线，每头牛都有它的坐标(范围:0..1,000,000,000)和种族(0或1)。一直以来FarmerJohn 查看详情

[bzoj]1639:[usaco2007mar]monthlyexpense月度开支

1639:[Usaco2007Mar]MonthlyExpense月度开支TimeLimit: 5Sec  MemoryLimit: 64MBSubmit: 1077  Solved: 533[Submit][Status][Discuss]DescriptionFarmerJohn是一个令人惊讶的会计学天才，他已经明 查看详情

[bzoj]1657:[usaco2006mar]mooo奶牛的歌声

1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec  MemoryLimit:64MBSubmit:858  Solved:603[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverystraigh 查看详情

[bzoj1657][usaco2006mar]mooo奶牛的歌声

 1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec  MemoryLimit:64MBSubmit:863  Solved:607[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverys 查看详情

bzoj1597[usaco2008mar]土地购买

[Usaco2008Mar]土地购买TimeLimit:10SecMemoryLimit:162MBDescription农夫John准备扩大他的农场,他正在考虑\(N(1<=N<=50,000)\)块长方形的土地.每块土地的长宽满足\((1<=宽<=1,000,000;1<=长<=1,000,000)\).每块土地的价格是它的面积,但FJ可以同... 查看详情

bzoj1637[usaco2007mar]balancedlineup*

bzoj1637[Usaco2007Mar]BalancedLineup题意：n头牛，第i头牛位置为ai，种族为bi（只能为0，1），求一个区间（按数轴位置），使得区间两端牛距离差最大且两种种族牛数相等。n≤50000。题解：按位置排序。然后利用前缀和sum[i][0]-sum[j-1][0]... 查看详情

[bzoj1617][usaco2008mar]rivercrossing渡河问题

1617:[Usaco2008Mar]RiverCrossing渡河问题TimeLimit:5Sec  MemoryLimit:64MBSubmit:1102  Solved:801[Submit][Status][Discuss]DescriptionFarmerJohn以及他的N(1<=N<=2,500)头奶牛打算过一条河，但他们所有的渡河工 查看详情

bzoj1597:[usaco2008mar]土地购买

BZOJ1597:[Usaco2008Mar]土地购买Description农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购买多快土地.这些土... 查看详情

bzoj1703:[usaco2007mar]rankingthecows奶牛排名传递闭包,bitset

1703:[Usaco2007Mar]RankingtheCows奶牛排名TimeLimit: 5Sec  MemoryLimit: 64MBSubmit: 323  Solved: 238[Submit][Status][Discuss]Description    农夫约翰有 查看详情

[bzoj3399][usaco2009mar]sandcastle城堡（排序）

3399:[Usaco2009Mar]SandCastle城堡TimeLimit: 3Sec  MemoryLimit: 128MBSubmit: 79  Solved: 66[Submit][Status][Discuss]Description约翰用沙子建了一座城堡．正如所有城堡的城墙，这城墙也有许多枪眼，两个相邻 查看详情

[bzoj1639][usaco2007mar]monthlyexpense月度开支

1639:[Usaco2007Mar]MonthlyExpense月度开支TimeLimit:5Sec  MemoryLimit:64MBSubmit:1069  Solved:530[Submit][Status][Discuss]DescriptionFarmerJohn是一个令人惊讶的会计学天才，他已经明白了他可能会花光他的钱，这些钱本来是要维持农场每 查看详情

[bzoj]1657:[usaco2006mar]mooo奶牛的歌声

1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit: 5Sec  MemoryLimit: 64MBSubmit: 867  Solved: 610[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsa 查看详情