hdu-1863-畅通工程(kruskal算法模板)

 1 /*
 2     Name:hdu-1863-畅通工程
 3     Copyright:
 4     Author:
 5     Date: 2018/4/18 10:19:03
 6     Description:
 7     kruskal算法 
 8 */
 9 #include <iostream>
10 #include <cstring>
11 #include <algorithm> 
12 #include <cstdio>
13 using namespace std;
14 const int MAXN = 110;
15 struct edge{
16     int x, y, w;
17     edge(int x=0,int y=0, int w=0):x(x),y(y),w(w){
18     };
19 } e[5000];
20 int N ,M, cnt;
21 int fa[MAXN];
22 int getfather(int x) {//查找 
23     if (x == fa[x]) return x;
24     else return fa[x] = getfather(fa[x]);
25 }
26 bool cmp(edge a, edge b)  {//从小到大排序 
27     return a.w < b.w;
28 }
29 int kruskal() {
30     sort(e+1, e+M+1, cmp);
31     cnt = M;//边数 
32     int ans = 0;
33     for (int i=1; i<=N; ++i) fa[i] = i;
34     for (int i=1; i<=M; ++i) {
35         int t1 = getfather(e[i].x);
36         int t2 = getfather(e[i].y);
37         if (t1 != t2) {
38             fa[t1] = t2;
39             ans += e[i].w;
40             cnt--;//加入结点 
41             if (cnt == 1) break;////// 加入n-1条边说明已经生成最小生成树 
42         }
43     }
44     return ans;
45 }
46 int main()
47 {
48 //    freopen("in.txt", "r", stdin);
49     while (cin>>N>>M, N) {
50         memset(e, 0, sizeof(e));
51         memset(fa, 0, sizeof(fa));
52         for (int i=1; i<=N; i++) {
53             scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].w);
54         }
55         int ans = kruskal();
56         if (cnt != 1) cout<<"?"<<endl;
57         else cout<<ans<<endl;
58     }
59     return 0;
60 }
61 
62