[题目链接]
思路：最大值的村村通，突然发现Kruskal算法不用处理重边，真是又一大优点啊！（手动点赞）
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int Max_n=1e3+10; const int Max_m=1e5+10; struct edge{ int from,to,cost; bool operator<(const edge& e)const{ return cost>e.cost; } }e[Max_m]; int N,M; int par[Max_n]; int Find(int x){ if(par[x]==x)return x; return par[x]=Find(par[x]); } int Kruskal(){ for(int i=0;i<N;i++)par[i]=i; int ans=0,sum=0; sort(e,e+M); for(int i=0;i<M;i++){ int x=Find(e[i].from); int y=Find(e[i].to); if(x!=y){ ans++;sum+=e[i].cost; par[x]=y; } if(ans==N-1)break; } if(ans<N-1)return -1; return sum; } int main() { scanf("%d%d",&N,&M); int a,b,c; for(int i=0;i<M;i++){ scanf("%d%d%d",&a,&b,&c); e[i].from=a-1;e[i].to=b-1; e[i].cost=c; } int f=Kruskal(); if(f==-1)printf("-1\n"); else printf("%d\n",f); return 0; }