关键词：
题目描述
Bessie is planning the annual Great Cow Gathering for cows all across the country and, of course, she would like to choose the most convenient location for the gathering to take place.
Each cow lives in one of N (1 <= N <= 100,000) different barns (conveniently numbered 1..N) which are connected by N-1 roads in such a way that it is possible to get from any barn to any other barn via the roads. Road i connects barns A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). The Great Cow Gathering can be held at any one of these N barns. Moreover, barn i has C_i (0 <= C_i <= 1,000) cows living in it.
When choosing the barn in which to hold the Cow Gathering, Bessie wishes to maximize the convenience (which is to say minimize the inconvenience) of the chosen location. The inconvenience of choosing barn X for the gathering is the sum of the distances all of the cows need to travel to reach barn X (i.e., if the distance from barn i to barn X is 20, then the travel distance is C_i*20). Help Bessie choose the most convenient location for the Great Cow
Gathering.
Consider a country with five barns with [various capacities] connected by various roads of varying lengths. In this set of barns, neither barn 3 nor barn 4 houses any cows.
1 3 4 5
@[email protected]@[email protected][2]
[1] |
2|@[1]2Bessie can hold the Gathering in any of five barns; here is the table of inconveniences calculated for each possible location:
Gather ----- Inconvenience ------
Location B1 B2 B3 B4 B5 Total
1 0 3 0 0 14 17
2 3 0 0 0 16 19
3 1 2 0 0 12 15
4 4 5 0 0 6 15
5 7 8 0 0 0 15
If Bessie holds the gathering in barn 1, then the inconveniences from each barn are:
Barn 1 0 -- no travel time there!
Barn 2 3 -- total travel distance is 2+1=3 x 1 cow = 3 Barn 3 0 -- no cows there!
Barn 4 0 -- no cows there!
Barn 5 14 -- total travel distance is 3+3+1=7 x 2 cows = 14 So the total inconvenience is 17.
The best possible convenience is 15, achievable at by holding the Gathering at barns 3, 4, or 5.
Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。
每个奶牛居住在 N(1<=N<=100,000) 个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1 <= A_i <=N; 1 <= B_i <= N),长度为L_i(1 <= L_i <= 1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住者C_i(0 <= C_i <= 1,000)只奶牛。
在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。
输入输出格式
输入格式：-
Line 1: A single integer: N
-
Lines 2..N+1: Line i+1 contains a single integer: C_i
- Lines N+2..2*N: Line i+N+1 contains three integers: A_i, B_i, and L_i
- Line 1: The minimum inconvenience possible
输入输出样例
5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 3
15
题解：树形dp;感觉洛谷上的题解比我讲的好，所以复制了一段：
思路就是先假设所有奶牛都到一个点了，然后就可以从这个点推出所有点的状态，O(n)的动态规划，其实就是一维（也可以不用数组），我们记录每个点他的所有儿子节点（包括儿子节点的节点）的奶牛总数son[i]，dp[v]=dp[rt]-son[v]*a[i].w+(sum-son[v])*a[i].w;（sum是所有奶牛数总和），预处理的时候我们把所有点到第一个点的距离，接下来就可以愉快的处理出dp[1]了，然后就是一边DFs的动态规划并且每次比较取答案。（感谢 cheeseYang）
考虑如果依次枚举每一个点作为集会的地点
使用DFS进行计算
然后再依次比较
时间复杂度O(n^2)
但是n的范围太大，显然会超时。
那么，我们应当如何优化？
先看看样例
通过一次O(n)的计算，很容易得出来
如果选择1号节点，答案就是17
既然O(n^2)的计算无法在时间内求解
那么是否可以递推出来呢？
显然是可以的。
观察如果已经知道1号节点所需的时间
那么，我们可以做如下假设：
① 所有的牛首先到达了1号节点
② 3号节点以及他子树上的节点都需要退回1->3的路径的长度
③ 除了3号节点以及他子树上的节点都需要前进1->3的路径的长度
通过上面的三条东西，我们就可以从任意一个父节点推出子节点的时间
所以，又是一遍O(n)的计算就可以推出最终的答案。（感谢 yybyyb）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 using namespace std; 6 #define man 200100 7 #define ll long long 8 ll n,m,a[man],ans=123456480,sum=0; 9 ll son[man],dis[man<<1]; 10 struct edge 11 { 12 ll next,to,dis; 13 }e[man]; 14 ll num=0,head[man<<2]; 15 ll f[man]; 16 inline void add(ll from,ll to,ll dis)//添边 17 { 18 e[++num].next=head[from]; 19 e[num].to=to; 20 e[num].dis=dis; 21 head[from]=num; 22 } 23 ll dfs(ll u,ll father)//找出所有关于1节点的距离和 24 { 25 ll tot=0; 26 for(ll i=head[u];i;i=e[i].next) 27 { 28 ll to=e[i].to; 29 if(to==father)continue; 30 ll d=dfs(to,u); 31 dis[u]+=dis[to]+e[i].dis*d; 32 tot+=d; 33 } 34 return son[u]=tot+a[u]; 35 } 36 void sch(ll u,ll father)//求出代价f[] 37 { 38 for(ll i=head[u];i;i=e[i].next) 39 { 40 ll to=e[i].to; 41 if(to==father)continue; 42 f[to]=f[u]-son[to]*e[i].dis+(sum-son[to])*e[i].dis;//方程 43 sch(to,u); 44 } 45 } 46 int main() 47 { 48 ios::sync_with_stdio(false); 49 cin.tie(0); 50 cin>>n; 51 for(int i=1;i<=n;i++) 52 { cin>>a[i];sum+=a[i];} 53 for(int i=1,x,y,d;i<n;i++) 54 { 55 cin>>x>>y>>d; 56 add(x,y,d);add(y,x,d); 57 } 58 memset(f,0,sizeof(f)); 59 dfs(1,1); 60 sch(1,1); 61 ans=f[1]; 62 for(int i=1;i<=n;i++) 63 ans=min(ans,f[i]); 64 cout<<ans+dis[1]<<endl; 65 return 0; 66 }
注：此题不能直接在main()中直接求f[]，因为此时并不知道f[1]的取值，所以仍需一次遍历。
p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)
题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然， 查看详情
洛谷p2986[usaco10mar]greatcowgat…(树形dp+容斥原理)
P2986[USACO10MAR]伟大的奶牛聚集GreatCowGat…题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace. 查看详情
p2986[usaco10mar]伟大的奶牛聚集（思维，dp）(代码片段)
题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方... 查看详情
p2986[usaco10mar]伟大的奶牛聚集greatcowgat…
典型树上dp，直接暴力算会超时，小心呀 #include<cstring>#include<iostream>#include<algorithm>#include<cstdio>#include<vector>#definemaxn100010usingnamespacestd;typedeflonglongll;structNode intp; lllen; Node(inta,llb):p(a),len(b);vec... 查看详情
bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)
【题解】 很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。 我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。 显然选择它的儿子... 查看详情
p2986[usaco10mar]伟大的奶牛聚集(代码片段)
题意：给一棵n个点的边+点权树，求带权重? 思路：其实这题和之前那个Sta有点像，我们同样只需要预处理出一个f[u]代表以u为集合点的方便程度，那么我们就可以O（1）的转移了假设v是u的儿子，f[v]=f[u]-(siz[v]*len)+(n-siz[v])... 查看详情
p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)
一道比较经典的题（蒟蒻的我没有一次切掉）…… 首先这道题要优化的原因就是数据范围，要是O(n2) “ 显然 ”会超时。。。 那么我们很不情愿不得已不开心地最终被迫考虑一下优化（说实话好多算法都... 查看详情
[usaco10mar]伟大的奶牛聚集
[USACO10MAR]伟大的奶牛聚集Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路... 查看详情
洛谷p3052[usaco12mar]摩天大楼里的奶牛cowsinaskyscraper
P3052[USACO12MAR]摩天大楼里的奶牛CowsinaSkyscraper题目描述AlittleknownfactaboutBessieandfriendsisthattheylovestairclimbingraces.Abetterknownfactisthatcowsreallydon‘tlikegoingdownstairs.Soafterthecowsfinishracingt 查看详情
洛谷p3052[usaco12mar]摩天大楼里的奶牛cowsinaskyscraper
题目描述AlittleknownfactaboutBessieandfriendsisthattheylovestairclimbingraces.Abetterknownfactisthatcowsreallydon‘tlikegoingdownstairs.Soafterthecowsfinishracingtothetopoftheirfavoriteskyscraper,theyhadap 查看详情
[usaco10mar]伟大的奶牛聚集-树形dp(代码片段)
每个点有重数，求到所有点距离最小的点就是魔改的重心了#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1000005;vector<pair<int,int>>g[N];intsiz[N],f[N],vis[N],sum[N],c[N],n,m,t1,t2,t3,tot;voiddfs1(intp)vis[p]=1;siz[p]=c[p];for(inti=0;i<... 查看详情
洛谷p2904[usaco08mar]跨河rivercrossing(代码片段)
题目动规方程f[i]=min(f[i],f[i?j]+sum)我们默认为新加一头牛，自占一条船。想象一下，它不断招呼前面的牛，邀请它们坐自己这条船，当且仅当所需总时间更短时，前一头奶牛会接受邀请，最多邀请前面的所有奶牛一起坐这条船。1#... 查看详情
bzoj1703[usaco2007mar]rankingthecows奶牛排名*
bzoj1703[Usaco2007Mar]RankingtheCows奶牛排名题意：n头奶牛，知道n对奶牛之间的产奶量大小，问想知道所有奶牛产奶量大小顺序至少还需知道几对。n≤1000。题解：每个大小关系看为一条有向边，对每头奶牛进行dfs，求每头奶牛可以到... 查看详情
bzoj3375[usaco2004mar]paranoidcows发疯的奶牛*
bzoj3375[Usaco2004Mar]ParanoidCows发疯的奶牛题意：依次给出n只奶牛的产奶时间段，求最大的k使得前k只奶牛不存在一个时间段被另一个时间段完全覆盖的情况。n≤100000。题解：设当前在处理第i只奶牛，前i-1只奶牛都合法。那么如果... 查看详情
[bzoj]1657:[usaco2006mar]mooo奶牛的歌声
1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec MemoryLimit:64MBSubmit:858 Solved:603[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverystraigh 查看详情
[bzoj]1616:[usaco2008mar]cowtravelling游荡的奶牛
1616:[Usaco2008Mar]CowTravelling游荡的奶牛TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 1312 Solved: 736[Submit][Status][Discuss]Description奶牛们在被划分成N行M列(2<=N<=100 查看详情
[bzoj1657][usaco2006mar]mooo奶牛的歌声
1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit:5Sec MemoryLimit:64MBSubmit:863 Solved:607[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsarestandinginaverys 查看详情
[usaco2010mar]gather奶牛大集会
[Usaco2010Mar]gather奶牛大集会题目Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条... 查看详情