最大生成树Bad Cowtractors_在线工具

bool cmp(edge a,edge b) {     return a.w>b.w; }

 1 #include<iostream>//poj头文件很烦银  2 #include<algorithm>  3 #include<stdio.h>  4 #include<cmath>  5 #include<queue>  6 #include<cstring>  7 #include<vector>  8 #include<map>  9 using namespace std; 10 const int num=1e5+10; 11 struct edge 12 { 13     int u; 14     int v; 15     int w; 16 }e[num];//存图 17 int s[num];//集合 18 int n,m; 19 int ans;//生成树权值 20 int cnt;//统计边数 21 bool cmp(edge a,edge b)//降序排列 22 { 23     return a.w>b.w; 24 } 25 int find_set(int x)//集合查找+路径压缩 26 { 27     if(x!=s[x]) 28     s[x]=find_set(s[x]); 29     return s[x]; 30 } 31 void kruskal() 32 { 33     for(int i=1;i<=n;i++)//集合初始化 34     s[i]=i; 35     sort(e+1,e+1+m,cmp); 36     for(int i=1;i<=m;i++) 37     { 38         int b=find_set(e[i].u); 39         int c=find_set(e[i].v); 40         if(b==c)//如果重边则跳过 41         continue; 42         s[c]=b;//合并集合 43         ans+=e[i].w;//累计权值 44         cnt++;//边+1 45         if(cnt==n-1)//联通至此结束 46         break; 47     } 48 } 49 int main() 50 { 51     cin>>n>>m; 52     for(int i=1;i<=m;i++) 53     { 54         scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w); 55     } 56     kruskal(); 57     if(cnt==n-1) 58     printf("%d\n",ans); 59     else//不连通输出-1 60     printf("%d\n",-1); 61     return 0; 62 }