题目链接 ：http://acm.hdu.edu.cn/showproblem.php?pid=1863
题目描述 :
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达性即可）。通过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。


输入值
测试输入包含一些测试用例。每个测试用例的第1行指定评估的道路条数N，村庄数目M（<100）；随后的N
行对应村庄间道路的成本，每行称为一对正为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。


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

样本输入
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100


样本输出
3
？

题解 :
/*
   最小生成树:
   特点(性质): 1、一个最小生成树,它的任意一颗子树都是最小生成树
               2、也就是一颗最小生成树,实际上是由很多最小生成树组成的
   解释    :   一个用(N - 1) 条边连接的且所有点到其他点的路径唯一。 
   用途    :   主要用来解决如何用最小的代价用 N - 1 条边连接 N 个点的问题 
   两种方法:   1、Kruskal算法 (用并查集判断是否会出现环贪心的选取) 
               2、Prim算法    (每次找到最小边权,进行标记,依次更新边权值) 
   结论    :   最小生成树是没有环的 
*/

// 方法一 : 
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string.h>
#include<string>
#include<limits.h>
#include<vector>
#include<deque>
#include<queue>
#include<cmath>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int maxn = 105;
struct rec {
    int x,y,z;
} edge[maxn];
int fa[maxn];
int n,m;
int main(void) {
    void solve();
    while(scanf("%d%d",&n,&m) != EOF) {
        if(n == 0) break;
        for(int i = 1; i <= n; i ++) {
            scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
        }
        solve();
    }
    return 0;
}
bool cmp(rec a,rec b) {
    return a.z < b.z;
}
int get(int x) {
    return x == fa[x] ? x : fa[x] = get(fa[x]);
}
void solve() {
    int ans = 0;
    sort(edge + 1,edge + 1 + n,cmp);
    for(int i = 1; i <= n; i ++) {
        fa[i] = i;
    }
    int t = 0;
    for(int i = 1; i <= n; i ++) {
        int xx = get(edge[i].x);
        int yy = get(edge[i].y);
        if(xx == yy) continue;
        fa[yy] = xx;
        ans += edge[i].z;
        t ++;                                        // 计算节点 
    }
    if(t == m - 1)                                   // 最小生成树的重要性质:一个用 n - 1 条边连接的且所有点到其他点的路径唯一 
        printf("%d\n",ans);
    else
        printf("?\n");
    return ;
}
/*
//  方法二: 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<limits.h>
#include<cstdio>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 105;
int a[maxn][maxn],d[maxn];
bool vis[maxn];
int n,m,ans,x,y,z;
int main(void) {
    bool prim(int pos);
    while(scanf("%d%d",&n,&m) != EOF) {
        if(n == 0) break;
        memset(vis,0,sizeof(vis));
        memset(a,0x3f,sizeof(a));           // 初始化为无穷大,以便于下面的比较 
        memset(d,0x3f,sizeof(d)); 
        for(int i = 1; i <= n; i ++) {
            scanf("%d%d%d",&x,&y,&z);
            a[x][y] = min(a[x][y],z);       // 输入的值或者点的坐标有可能重复,所以需要每次取一下最小值 
            a[y][x] = min(a[y][x],z);
        }
        bool flag = prim(1);
        if(flag) {
            printf("%d\n",ans);
        } else {
            printf("?\n");
        }
    }
    return 0;
}
bool prim(int pos) {
    int cur;
    ans = 0,d[pos] = 0;
    for(int i = 1; i <= m; i ++) {
        cur = -1;
        for(int j = 1; j <= m; j ++) {                      // 寻找最小花费的先边 
            if(!vis[j] && (cur == -1 || d[j] < d[cur])) {
                cur = j;
            }
        }
        ans += d[cur];                                      // 如果说存在一个最小生成树,那么说明最后求得的最低成本一定是 < INF 的 
        vis[cur] = 1;
        for(int k = 1; k <= m; k ++) {                      // 更新边权最小值 
            if(!vis[k]) {                                   // 这里进行标记一下,时间复杂度会更快一点 
                d[k] = min(d[k],a[cur][k]);                 // 通过上面我已经找到边权,然后接下来我可以依次(从cur -- > k)更新 
            }                                    
        }
    }
    if(ans < INF) return true;
    else return false;
}

*/