【最小生成树+kruskal】杭电 hdu 1863 畅通工程

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//    Copyright (c) 2012 panyanyany All rights reserved.    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1863    Name  : 1863 畅通工程    Date  : Monday, February 6, 2012    Time Stage : half an hour    Result: 53204292012-02-06 10:00:29Accepted18630MS188K2039 BC++pyyTest Data :Review ://----------------------------------------*/#include <cstdio>#include <stdlib.h>#include <string.h>#include <algorithm>using namespace std ;#define MEM(a, v)memset (a, v, sizeof (a))// a for address, v for value#define max(x, y)((x) > (y) ? (x) : (y))#define min(x, y)((x) < (y) ? (x) : (y))#define INF(0x3f3f3f3f)#define MAXN(103)#define MAXE(MAXN*MAXN)#define DEBUG/##/struct EDGE {int u, v, w ;bool operator< (const EDGE &e) {return w < e.w ;}};intn, m ;intset[MAXN] ;intmap[MAXN][MAXN] ;EDGEedge[MAXE] ;int find (int x){if (x == set[x])return x ;return set[x] = find(set[x]) ;// 压缩路径}inline void merge (int x, int y){set[x] = set[y] ;}int kruskal (){int i, sum, edgeCnt ;// 将边排序sort (edge, edge+n) ;// 并查集初始化，每个点自成集合，根结点为自己for (i = 1 ; i <= m ; ++i)set[i] = i ;sum = edgeCnt = 0 ;for (i = 0 ; i < n ; ++i){// 查找各集合的根结点int x = find (edge[i].u) ;int y = find (edge[i].v) ;// 根结点不同，则所在集合不同if (x != y){// 合并两个不同的集合merge (x, y) ;sum += edge[i].w ;// 所有集合中的边数++edgeCnt ;// 若边数等于 m-1，表示所有点都在一个集合中了if (m-1 == edgeCnt)break ;}}// 边数小于m-1，表示有两个以上集合不能合并if (m-1 > edgeCnt)return INF ;return sum ;}int main (){int i ;int ans ;while (scanf ("%d%d", &n, &m), n){for (i = 0 ; i < n ; ++i)scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w) ;ans = kruskal () ;if (INF == ans)puts ("?") ;elseprintf ("%d\n", ans) ;}return 0 ;}