POJ 1251 Jungle Roads 最小生成树

题意：

　　第一行给一个N，代表这里有N- 1 个村庄，接下来有 N- 1 行，每行开头输入一个大写字母 C 代表第 i 个村庄的编号，随后有一个数字 m 代表 C 这个村庄和 m 个村庄相连，随后再给出 m 组数据，每组输入由一个大写字母 F 和数字 w 组成，代表 C 和 F 之间的距离为 W；当N== 0时程序结束。

思路：

　　因为题目中给出的字母为 A - Z 那么我这里用数字 1 - 26代替村庄的编号，然后求最小生成树。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <cctype>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <stack>
10 #include <map>
11 #include <set>
12 using namespace std;
13 
14 const int MAXN = 29;
15 int pre[MAXN];
16 int n,m;
17 structNode   //储存数据
18 {
19     int u, v, w;
20 }cy[103];
21 
22 void debug()
23 {
24      for(int i =1; i<m; i++)
25             cout << cy[i].u << " "<< cy[i].v <<" "<< cy[i].w <<endl;
26 }
27 
28 int Find(int x)     //并查集
29 {
30     return x == pre[x] ? x :(pre[x] = Find(pre[x]));
31 }
32 
33 int mycmp(Node a,Node b)
34 {
35     return a.w < b.w;
36 }
37 
38 void mst()
39 {
40     for(int i = 0 ; i < MAXN; i++)
41         pre[i] = i;
42 }
43 
44 int kru()
45 {
46     int ans = 0;
47     int cnt = 0;
48     sort(cy + 1, cy + m , mycmp);
49     //cout << endl;
50     //debug();
51     for(int i = 1; i < m; i++)       //从最小的那条边开始寻找
52     {
53         int fv = Find(cy[i].v);
54         int fu = Find(cy[i].u);
55         if(fv != fu)               //如果不在一个集合就把当前这条比较小的加进去
56         {
57             pre[fv] = fu;
58             ans += cy[i].w;
59             cnt ++;
60         }
61         if(cnt == n -1)      //构成了最小生成树
62         {
63             break;
64         }
65     }
66     return ans;
67     //cout <<"ans " <<  ans <<endl;
68 }
69 
70 
71 int main()
72 {
73     //freopen("in.cpp","r",stdin);
74     while(cin >> n && n)
75     {
76         mst();
77         m = 1;
78         for(int j = 1; j < n; j++)
79         {
80             char s[29][3] = {0};
81             cin >> s[0];
82             int k;
83             cin >> k;
84             for(int i = 1; i <= k; i++)
85             {
86                 int wh;
87                 cin >> s[i] >> wh;
88                 cy[m].u = s[0][0] - 'A' + 1;
89                 cy[m].v = s[i][0] - 'A' + 1;
90                 cy[m].w = wh;
91                 m++;
92             }
93         }
94        cout << kru() << endl;
95     }
96     return 0;
97 }