poj1287Networking（最小生成树）

模板题。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=55;
 6 const int maxe=10010;  //1010不够！！
 7 int n,m;
 8 int f[maxn];
 9 struct edge
10 {
11     int u,v,w;
12 }e[maxe];
13 
14 bool cmp(edge a,edge b)
15 {
16     return a.w<b.w;
17 }
18 
19 void init()
20 {
21     for(int i=0;i<=n;i++)
22         f[i]=i;
23 }
24 
25 int gf(int s)
26 {
27     return s==f[s]?s:f[s]=gf(f[s]);
28 }
29 
30 void uni(int a,int b)
31 {
32     int pa=gf(a);
33     int pb=gf(b);
34     f[pa]=pb;
35 }
36 
37 int main()
38 {
39     while(scanf("%d",&n)&&n)
40     {
41         init();
42         scanf("%d",&m);
43         int ans=0;
44         for(int i=0;i<m;i++)
45             scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
46         sort(e,e+m,cmp);
47         for(int i=0;i<m;i++)
48             if(gf(e[i].u)!=gf(e[i].v))
49         {
50             ans+=e[i].w;
51             uni(e[i].u,e[i].v);
52         }
53         printf("%d
",ans);
54     }
55 }