poj1251Jungle Roads（最小生成树）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn=28;
 7 const int maxe=88;
 8 int f[maxn];
 9 int n;
10 struct edge
11 {
12     int u,v,w;
13 }e[maxe];
14 
15 bool cmp(edge a,edge b)
16 {
17     return a.w<b.w;
18 }
19 
20 void init()
21 {
22     for(int i=0;i<=n;i++)
23         f[i]=i;
24 }
25 
26 int gf(int s)
27 {
28     return s==f[s]?s:f[s]=gf(f[s]);
29 }
30 
31 void uni(int a,int b)
32 {
33     int pa=gf(a);
34     int pb=gf(b);
35     f[pa]=pb;
36 }
37 
38 int main()
39 {
40      while(scanf("%d",&n)&&n)
41     {
42         init();
43         int ans=0;
44         int cnt=0;
45         char ch[2],s[2];
46         int x,v,w;
47         for(int i=0;i<n-1;i++)
48         {
49             scanf("%s",ch);
50             int u=int(ch[0]-'A');
51             scanf("%d",&x);
52             for(int j=0;j<x;j++)
53             {
54                 scanf("%s%d",s,&w);
55                 v=int (s[0]-'A');
56                 e[cnt].u=u;
57                 e[cnt].v=v;
58                 e[cnt].w=w;
59                 cnt++;
60             }
61         }
62         sort(e,e+cnt,cmp);
63         for(int i=0;i<cnt;i++)
64         {
65             if(gf(e[i].u)!=gf(e[i].v)) {
66                 ans+=e[i].w;
67                 uni(e[i].u,e[i].v);
68             }
69         }
70         printf("%d
",ans);
71     }
72 }