题目描述
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找出最方便的地点来举行大集会。 考虑一个由五个农场组成的国家,分别由长度各异的道路连接起来。在所有农场中,3号和4号没有奶牛居住。
输入
第一行:一个整数N * 第二到N+1行:第i+1行有一个整数C_i * 第N+2行到2*N行,第i+N+1行为3个整数:A_i,B_i和L_i。
输出
* 第一行:一个值,表示最小的不方便值。
样例输入
5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3
样例输出
15
这是一道入门的树上问题。首先说一下暴力,以每一个点为根对整棵树做一遍dfs,最后找出最优解,时间复杂度是O(n^2)。但显然并不用这么麻烦,对于以i为集会点的结果,如果把集会点移向与i相连的点j,那么,把这条连接i与j的边断开后可以把整个树变成两个联通块。把集会点从i移向j后,i所在联通块所有点费用要加上这条边边权费用,j所在联通块所有点费用要减掉这条边边权的费用。那么只要处理出一个点的结果,再O(n)转移就可以了。以一个点为根,dfs向子节点转移,对于一个节点i转移到它的一个子节点j,两个联通块节点数分别是以j为根的子树节点数和总节点数-以j为根的子树节点数。
最后附上代码。
#include<queue> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; long long size[100010]; int head[100010]; int next[200010]; int to[200010]; long long val[200010]; int f[100010]; long long s[100010]; long long a[100010]; int x,y; long long v; int n; int tot; long long sum; long long ans; void add(int x,int y,long long v) { tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y; val[tot]=v; } void dfs(int x,int fa) { f[x]=fa; for(int i=head[x];i;i=next[i]) { if(to[i]!=fa) { dfs(to[i],x); size[x]+=size[to[i]]; } } } void dfs2(int x,long long dep) { ans+=dep*a[x]; for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x]) { dfs2(to[i],dep+val[i]); } } } void find(int x) { for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x]) { s[to[i]]=s[x]-size[to[i]]*val[i]+(sum-size[to[i]])*val[i]; find(to[i]); } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&size[i]); a[i]=size[i]; sum+=size[i]; } for(int i=1;i<n;i++) { scanf("%d%d%lld",&x,&y,&v); add(x,y,v); add(y,x,v); } dfs(1,1); dfs2(1,0ll); s[1]=ans; find(1); ans=1ll<<62; for(int i=1;i<=n;i++) { ans=min(ans,s[i]); } printf("%lld",ans); }