【最小生成树+Prim】杭电 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  : Sunday, February 5, 2012    Time Stage : half an hour    Result: 53174622012-02-05 14:07:12Accepted18630MS212K1820 BC++pyy53174442012-02-05 14:04:25Wrong Answer18630MS212K1761 BC++pyyTest Data :Review :还是最小生成树，不过跟hdu 1233比有些细节要注意～//----------------------------------------*/#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/##/intn, m ;intused[MAXN], q[MAXN], dist[MAXN] ;intmap[MAXN][MAXN] ;int Prim (){int i, j, iMinPath, MinPath, sum ;MEM (used, 0) ;for (i = 1 ; i <= m ; ++i)dist[i] = map[1][i] ;//dist[0] = INF ;used[1] = true ;sum = 0 ;for (i = 1 ; i <= m-1 ; ++i){MinPath = INF ;iMinPath = 1 ;// 由于可能有不能连通的点，所以 iMInPath 要初始化for (j = 1 ; j <= m ; ++j)if (!used[j] && dist[j] < MinPath){MinPath = dist[j] ;iMinPath = j ;}used[iMinPath] = true ;sum += MinPath ;if (INF == MinPath)// 已经没有可通的路，由于 iMinPath 初始化为 1break ;// 继续循环下去会改变 dist 里的数据，所以要及时跳出for (j = 1 ; j <= m ; ++j)if (!used[j] && dist[j] > map[iMinPath][j])dist[j] = map[iMinPath][j] ;}return sum ;}int main (){int i ;int x, y, c ;int ans ;while (scanf ("%d%d", &n, &m), n){MEM (map, INF) ;for (i = 1 ; i <= n ; ++i){scanf ("%d%d%d", &x, &y, &c) ;map[x][y] = map[y][x] = min(map[x][y], c) ;}ans = Prim () ;if (ans >= INF)puts ("?") ;elseprintf ("%d\n", ans) ;}return 0 ;}