关键词：
题目描述
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.
Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。
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.
每个奶牛居住在 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)只奶牛。
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.
在选择集会的地点的时候，Bessie希望最大化方便的程度(也就是最小化不方便程度)。比如选择第X个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和，(比如，农场i到达农场X的距离是20，那么总路程就是C_i*20)。帮助Bessie找出最方便的地点来举行大集会。
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] 2 Bessie 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.
输入输出格式
输入格式：
* 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
第一行：一个整数 N 。
第二到 N+1 行：第 i+1 行有一个整数 C_i
第 N+2 行到 2*N 行：第 i+N+1 行为 3 个整数：A_i,B_i 和 L_i。
输出格式：
* Line 1: The minimum inconvenience possible
第一行：一个值，表示最小的不方便值。
输入输出样例
输入样例#1： 复制 5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 3 输出样例#1： 复制 15
题意：
在一棵树上找一个点，使得其余各点到该点的加权路径最小。
思路：
思维题，先统计其余各点到根节点的路径总和，时间复杂度O(n)。
然后根据根节点的路径总和向其他节点扩散（dp），求出树上其余节点到固定节点的路径和，时间复杂度O(n)。
#include<bits/stdc++.h> #define mp make_pair #define pb push_back using namespace std; #define int long long const int inf=1e18; int cnt[100005],f[100005],dp[100005]; int c[100005]; int vis[100005]; vector<pair<int,int> > ed[100005]; int tot=0; int n; void dfs(int u) vis[u]=1; cnt[u]+=c[u]; for(auto to:ed[u]) int nxt=to.first,d=to.second; if(!vis[nxt]) dfs(nxt); cnt[u]+=cnt[nxt]; f[u]+=f[nxt]+cnt[nxt]*d; void dfs2(int u) vis[u]=1; for(auto to:ed[u]) int nxt=to.first,d=to.second; if(!vis[nxt]) dp[nxt]=min(dp[nxt],dp[u]-cnt[nxt]*d+(tot-cnt[nxt])*d); dfs2(nxt); signed main() scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&c[i]); for(int i=1;i<=n-1;i++) int a,b,l; scanf("%lld %lld %lld",&a,&b,&l); ed[a].pb(mp(b,l)); ed[b].pb(mp(a,l)); dfs(1); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) dp[i]=inf; tot=cnt[1]; dp[1]=f[1]; dfs2(1); int ans=inf; for(int i=1;i<=n;i++) ans=min(ans,dp[i]); printf("%lld ",ans); return 0;
p2986[usaco10mar]伟大的奶牛聚集greatcowgat…(代码片段)
题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace.Bessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然， 查看详情
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... 查看详情
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条道路... 查看详情
洛谷p2986[usaco10mar]greatcowgat…(树形dp+容斥原理)
P2986[USACO10MAR]伟大的奶牛聚集GreatCowGat…题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace. 查看详情
bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)
【题解】 很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。 我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。 显然选择它的儿子... 查看详情
[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<... 查看详情
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条... 查看详情
[bzoj]1657:[usaco2006mar]mooo奶牛的歌声
1657:[Usaco2006Mar]Mooo奶牛的歌声TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 867 Solved: 610[Submit][Status][Discuss]DescriptionFarmerJohn‘sN(1<=N<=50,000)cowsa 查看详情
洛谷p3052[usaco12mar]摩天大楼里的奶牛cowsinaskyscraper
P3052[USACO12MAR]摩天大楼里的奶牛CowsinaSkyscraper题目描述AlittleknownfactaboutBessieandfriendsisthattheylovestairclimbingraces.Abetterknownfactisthatcowsreallydon‘tlikegoingdownstairs.Soafterthecowsfinishracingt 查看详情
bzoj3401[usaco2009mar]lookup仰望*
bzoj3401[Usaco2009Mar]LookUp仰望题意：约翰的N头奶牛站成一排，奶牛i的身高是Hi。对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j。求出每只奶牛离她最近的仰望对象。n≤100000.题解：用一个单调栈维护即可... 查看详情