【最小生成树+kruskal】杭电 hdu 1233 还是畅通工程
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2012 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1233 Name : 1233 还是畅通工程 Date : Monday, February 06, 2012 Time Stage : half an hour Result: 53203582012-02-06 09:30:05Accepted1233125MS244K1671 BC++pyyTest Data :Review :还是Prim算法快啊！//----------------------------------------*/#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 ;intused[MAXN], set[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+m) ;// 并查集初始化，每个独立集的根结点都是自己for (i = 1 ; i <= n ; ++i)set[i] = i ;sum = edgeCnt = 0 ;for (i = 0 ; i < m ; ++i){// 查找 u 和 v 所在集合的根结点int x = find(edge[i].u) ;int y = find(edge[i].v) ;// 若根结点不同，表示存在两个独立的集合，则合并之～if (x != y){// 合并操作merge (x, y) ;// 合并则意味着新边的加入sum += edge[i].w ;// 边数加1++edgeCnt ;// 若边数满足条件，则表示所有的点都合并到一个集合中了，可以退出了if (n-1 == edgeCnt)break ;}}return sum ;}int main (){int i ;while (scanf ("%d", &n), n){m = n*(n-1)/2 ;for (i = 0 ; i < m ; ++i)scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w) ;printf ("%d\n", kruskal()) ;}return 0 ;}