这道题用的是并查集，刚刚看到这道题的时候想起来自己OJ的一道有点相似的题，说是每条边有一个等级，两个点之间的连接等级为路径上所有边的最高等级，很像，但是因为这道题的边有权值而且还要算最大值，结果自己这个想法就只是想了想，然后看了别人的解题报告，还真是并查集，看来自己的第一反应还挺重要的，把边降序排序，这样保证新加的一条边肯定是最短的，分别对这条边连接的两个点作为这一部分中选中的点找最优值，直到把所有的边加完
View Code
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 #define N 200005 6 #define max(a,b) ((a)>(b)?(a):(b)) 7 using namespace std; 8 struct node 9 { 10 long long u,v; 11 long long w; 12 }; 13 node e[N]; 14 int cmp(const void *a,const void *b) 15 { 16 node *c=(node *)a; 17 node *d=(node *)b; 18 if(d->w>c->w) 19 return 1; 20 else 21 return -1; 22 } 23 long long f[N],num[N]; 24 long long sum[N]; 25 void init() 26 { 27 int i; 28 for(i=1;i<N;i++) 29 { 30 f[i]=i; 31 sum[i]=0; 32 num[i]=1; 33 } 34 } 35 long long find(long long x) 36 { 37 long long r=x; 38 while(r!=f[r]) 39 { 40 r=f[r]; 41 } 42 long long t1; 43 while(x!=f[x]) 44 { 45 t1=f[x]; 46 f[x]=r; 47 x=t1; 48 } 49 return r; 50 } 51 int main() 52 { 53 long long n,i,j,k,fa,fb; 54 long long ans; 55 long long atob,btoa; 56 while(scanf("%lld",&n)!=EOF) 57 { 58 init(); 59 for(i=0;i<n-1;i++) 60 { 61 scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w); 62 } 63 qsort(e,n-1,sizeof(node),cmp); 64 ans=0; 65 for(i=0;i<n-1;i++) 66 { 67 fa=find(e[i].u); 68 fb=find(e[i].v); 69 atob=num[fa]*e[i].w+sum[fb]; 70 btoa=num[fb]*e[i].w+sum[fa]; 71 if(atob>btoa) 72 { 73 f[fa]=fb; 74 sum[fb]=atob; 75 num[fb]+=num[fa]; 76 } 77 else 78 { 79 f[fb]=fa; 80 sum[fa]=btoa; 81 num[fa]+=num[fb]; 82 } 83 ans=max(ans,max(atob,btoa)); 84 } 85 printf("%lld\n",ans); 86 } 87 return 0; 88 }