厦门购买域名以后搭建网站,注册公司都需要什么材料,手机跳转网站建设,软件外包专业[Usaco2010 Mar]gather 奶牛大集会 Bessie正在计划一年一度的奶牛大集会#xff0c;来自全国各地的奶牛将来参加这一次集会。当然#xff0c;她会选择最方便的地点来举办这次集会。每个奶牛居住在 N(1N100,000) 个农场中的一个#xff0c;这些农场由N-1条道路连接来自全国各地的奶牛将来参加这一次集会。当然她会选择最方便的地点来举办这次集会。每个奶牛居住在 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号没有奶牛居住。 分析 先以1随便为根dfs一次求出以每个节点为根时他所在的子树的人数个数sz并且计算出以1为根时的不方便度。 第二次时继续以1为根这时假设当前节点为x不方便度为cost儿子节点为y。把x的不方便度cost向y转化其实就是 cost(sz[1]-2*sz[y])*edge[i].cost 画个图就知道了。。。 #include set
#include map
#include list
#include cmath
#include queue
#include stack
#include string
#include vector
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;typedef long long ll;
typedef unsigned long long ull;#define debug puts(here)
#define rep(i,n) for(int i0;in;i)
#define rep1(i,n) for(int i1;in;i)
#define REP(i,a,b) for(int ia;ib;i)
#define foreach(i,vec) for(unsigned i0;ivec.size();i)
#define pb push_back
#define RD(n) scanf(%d,n)
#define RD2(x,y) scanf(%d%d,x,y)
#define RD3(x,y,z) scanf(%d%d%d,x,y,z)
#define RD4(x,y,z,w) scanf(%d%d%d%d,x,y,z,w)
#define All(vec) vec.begin(),vec.end()
#define MP make_pair
#define PII pairint,int
#define PQ priority_queue
#define cmax(x,y) x max(x,y)
#define cmin(x,y) x min(x,y)
#define Clear(x) memset(x,0,sizeof(x))
/*#pragma comment(linker, /STACK:1024000000,1024000000)int size 256 20; // 256MB
char *p (char*)malloc(size) size;
__asm__(movl %0, %%esp\n :: r(p) );*//******** program ********************/const int MAXN 1e55;
const ll INF 1e15;struct Edge{int y,cost,next;
}edge[MAXN1];int c[MAXN],n;
ll dp[MAXN],sz[MAXN],ans[MAXN];
int po[MAXN],tol;inline void add(int x,int y,int cost){edge[tol].y y;edge[tol].cost cost;edge[tol].next po[x];po[x] tol;
}void dfsDp(int x,int fa){dp[x] 0;sz[x] c[x];for(int ipo[x];i;iedge[i].next){int y edge[i].y;if(yfa)continue;dfsDp(y,x);sz[x] sz[y];dp[x] sz[y]*edge[i].costdp[y];}
}void dfsAns(int x,int fa,ll cost){ans[x] cost;for(int ipo[x];i;iedge[i].next){int y edge[i].y;if(yfa)continue;ll tmp cost(sz[1]-2*sz[y])*edge[i].cost;dfsAns(y,x,tmp);}
}int main(){#ifndef ONLINE_JUDGEfreopen(sum.in,r,stdin);//freopen(sum.out,w,stdout);
#endifwhile(~RD(n)){rep1(i,n)RD(c[i]);int x,y,cost;REP(i,2,n){RD3(x,y,cost);add(x,y,cost);add(y,x,cost);}dfsDp(1,0);dfsAns(1,0,dp[1]);ll tmp INF;rep1(i,n)cmin(tmp,ans[i]);couttmpendl;}return 0;
}转载于:https://www.cnblogs.com/yejinru/p/3295971.html
