关键词：
bzoj1827[Usaco2010 Mar]gather 奶牛大集会
题意：
n点树（有边权），找出一个点，使得其它所有点到它的距离和最小。n≤100000。
题解：
类似bzoj1131，但维护深度和改为维护距离和。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 #define ll long long 8 using namespace std; 9 10 inline int read(){ 11 char ch=getchar(); int f=1,x=0; 12 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} 13 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar(); 14 return f*x; 15 } 16 struct e{int t; ll w; int n;}es[maxn*2]; int g[maxn],ess; 17 void pe(int f,int t,ll w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;} 18 ll ds[maxn],sz[maxn],fads[maxn],dep[maxn],c[maxn],sum; int n,ans,fa[maxn]; 19 void dfs1(int x){ 20 sz[x]=c[x]; ds[x]=0; 21 for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x]){ 22 fa[es[i].t]=x; dep[es[i].t]=dep[x]+es[i].w; dfs1(es[i].t); 23 sz[x]+=sz[es[i].t]; ds[x]+=ds[es[i].t]+sz[es[i].t]*es[i].w; 24 } 25 } 26 void dfs2(int x,ll a,ll b){ 27 fads[x]=a+b*(sum-sz[x]); ll sm=fads[x]; 28 for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x])sm+=ds[es[i].t]+es[i].w*sz[es[i].t]; 29 for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa[x])dfs2(es[i].t,sm-(ds[es[i].t]+es[i].w*sz[es[i].t]),es[i].w); 30 } 31 int main(){ 32 n=read(); inc(i,1,n)c[i]=read(),sum+=c[i]; 33 inc(i,1,n-1){int x=read(),y=read(),z=read(); pe(x,y,z); pe(y,x,z);} dfs1(1); dfs2(1,0,0); 34 ans=1; inc(i,2,n)if(fads[i]+ds[i]<fads[ans]+ds[ans])ans=i; printf("%lld",fads[ans]+ds[ans]); return 0; 35 }
20160821
嘴巴题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 查看详情