嘉兴网站建设服务,wordpress apache 配置,企业网站建设需要许可证吗,上外贸网站建设Description Bessie正在计划一年一度的奶牛大集会#xff0c;来自全国各地的奶牛将来参加这一次集会。当然#xff0c;她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1N100,000) 个农场中的一个#xff0c;这些农场由N-1条道路连接#xff0c;并且从任意一…Description Bessie正在计划一年一度的奶牛大集会来自全国各地的奶牛将来参加这一次集会。当然她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1N100,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号没有奶牛居住。 Input 第一行一个整数N * 第二到N1行第i1行有一个整数C_i * 第N2行到2*N行第iN1行为3个整数A_i,B_i和L_i。 Output * 第一行一个值表示最小的不方便值。 题解不难发现选定点必须是树的带权重心 任意儿子大小不能超过总和一半. 直接 DFS 求重心并算一下贡献即可. #include bits/stdc.h
#define setIO(s) freopen(s.in,r,stdin)
#define maxn 1000000
#define inf 100000000000000
#define ll long long
using namespace std;
ll f[maxn], siz[maxn], sumv[maxn];
int C[maxn], hd[maxn], to[maxn 1], nex[maxn 1], val[maxn 1];
int n, edges, root;
ll tot;
void add(int u, int v, int c)
{nex[edges] hd[u], hd[u] edges, to[edges] v, val[edges] c;
}
void dfs(int u, int ff)
{siz[u] C[u], f[u] 0; for(int i hd[u]; i ; i nex[i]) {int v to[i]; if(v ff) continue; dfs(v, u); siz[u] siz[v];f[u] max(f[u], siz[v]); } f[u] max(f[u], tot - siz[u]); if(f[u] f[root]) root u;
}
void calc(int u,int ff)
{siz[u] C[u], sumv[u] 0; for(int i hd[u]; i ; i nex[i]){int v to[i]; if(v ff) continue; calc(v, u); siz[u] siz[v]; sumv[u] sumv[v] val[i] * siz[v]; }
}
int main()
{// setIO(input); scanf(%d,n); for(int i 1; i n; i) scanf(%d,C[i]), tot C[i]; for(int i 1, u, v, c; i n; i) {scanf(%d%d%d,u,v,c); add(u, v, c); add(v, u, c); }f[0] inf, root 0, dfs(1, 0);memset(siz, 0, sizeof(siz)), calc(root, 0); printf(%lld\n,sumv[root]); return 0;
}转载于:https://www.cnblogs.com/guangheli/p/10982700.html
