1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define MAXN 55 7 #define MAXM 10000 8 int fa[MAXN]; 9 int n,m,e,ans;10 struct Edge11 {12     int u;13     int v;14     int c;15 }p[MAXM];16 void addEdge(int u,int v,int c)17 {18     p[e].v=v;p[e].c=c;p[e].u=u;19     e++;20 }21 void init()22 {23     for(int i=0;i<=n;i++)24         fa[i]=i;25 }26 int find(int x)//查找点所在的集合27 {28     if(fa[x]!=x)29         fa[x]=find(fa[x]);30     return fa[x];31 }32 int cmp(const Edge &a,const Edge & b)33 {34     return a.c<b.c;35 }36 bool kru(int n,int m)37 {38     int i,j;39     sort(p,p+m,cmp);40     ans=0;41     init();42     int cnt=0;43     for(i=0;i<m;i++)44     {45     //使用并查集的地方，在每次加入边之前先判断下点是否已经在同    //一个集合了46         int uu=find(p[i].u);47         int vv=find(p[i].v);48         if(uu==vv)49             continue;50         fa[uu]=vv;51         ans+=p[i].c;52         cnt++;53     }54     if(cnt != n-1)55         return false;56     else57         return true;58 }59 int main()60 {61     while(scanf("%d",&n))62     {63         e=0;64         if(!n)65             break;66         scanf("%d",&m);67         for(int i=0;i<m;i++)68         {69             int a,b,c;70             scanf("%d%d%d",&a,&b,&c);71             addEdge(a,b,c);72         }73         kru(n,m);74         printf("%d\n",ans);75     }76     return 0;77 }