题目描述

题目大意

给定一张无向图 G=(n,n−1) G = ( n , n − 1 ) ，每个点上有一定的人，选定一个点，使得所有人走到那里的代价最小。

解题思路

30分思路 最短路, O(n3) O ( n 3 ) 30~60分思路 最短路 O(n2logn) O ( n 2 l o g n ) 60分思路 从每个点出发 dfs d f s 遍历 O(n2) O ( n 2 ) 100分思路 从1节点出发 dfs d f s 遍历，再根据结果进行递推，复杂度 O(n) O ( n )

100分代码

#include<cstdio> #include<cstring> #define N 100001 #define M 200001 using namespace std; struct node{int next,to,w;}e[M];int l[M],a[N],n,tot,ansi; long long ans=2147483647456465234557ll,f[N],rs[N],jl[N]; bool vis[N]; void add(int u,int v,int w) { e[tot]={l[u],v,w};l[u]=tot++; e[tot]={l[v],u,w};l[v]=tot++; return; } void dfs(int x,int dep)//从1节点遍历 { vis[x]=true; jl[x]=a[x]*dep;rs[x]=a[x];//求出每个节点下面的子树的人数 for(int i=l[x];~i;i=e[i].next) { int y=e[i].to; if(!vis[y]) dfs(y,dep+e[i].w),jl[x]+=jl[y],rs[x]+=rs[y];//加上其子树的值 } } void fdfs(int x,int fa,int w)//dfs转移，表示从第fa节点转移到x节点以及连接它们之间的w { vis[x]=true; if(x!=1) f[x]=f[fa]+rs[1]*w-2*rs[x]*w;//转移一个点，其代价等于其父亲的值加上全部人乘上这条边（全部人都跑过来了），同时要减去这个点下面的人乘这条边乘2（本来是要走的，现在不仅不要走了，所以要减去2倍） if(f[x]<ans) {ans=f[x];ansi=x;}//保存答案 for(int i=l[x];~i;i=e[i].next) { int y=e[i].to; if(!vis[y]) fdfs(y,x,e[i].w);//继续遍历 } } int main() { memset(l,-1,sizeof(l)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1,x,y,z;i<n;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z); dfs(1,0); memset(vis,0,sizeof(vis));//记得清0 f[0]=1e9; f[1]=jl[1]; fdfs(1,0,0); printf("%d\n%lld",ansi,ans); }