杭电 1863 畅通工程（最小生成树）

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

3 3

1 2 1

1 3 2

2 3 4

1 3

2 3 2

0 100

Sample Output

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 int fa[100000];
 5 struct stu
 6 {
 7     int from,to;
 8     int al;
 9 }st[100000];
10 int find(int a)
11 {
12     if(a == fa[a])
13         return a;
14     else
15         return fa[a]=find(fa[a]);
16 }
17 bool cmp(stu a,stu b)
18 {
19     return a.al<b.al;
20 }
21 int main()
22 {
23     int n,m,i;
24     while(scanf("%d %d",&n,&m) && n)
25     {
26         int sum=0;
27         for(i = 1 ; i <= m ;i++)
28         {
29             fa[i]=i;
30         }
31         for(i = 0 ; i < n ; i++)
32         {
33             scanf("%d %d %d",&st[i].from,&st[i].to,&st[i].al);
34         }
35         sort(st,st+n,cmp);
36         int k=0;
37         for(i = 0 ; i < n ;i++)
38         {
39             if(k == m-1)
40                 break;
41             if(find(st[i].from) != find(st[i].to))
42             {
43                 fa[st[i].from]=st[i].to;
44                 sum+=st[i].al;
45                 k++;
46             }
47         }
48         if(k == m-1)
49             printf("%d
",sum);
50         else
51             printf("?
");
52     }
53 }