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

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//    Copyright (c) 2012 panyanyany All rights reserved.    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1879    Name  : 1879 继续畅通工程    Date  : Monday, February 6, 2012    Time Stage : half an hour    Result:                                                                                                                                                                                                                                                                                                                                              53205392012-02-06 10:34:06Accepted1879281MS236K2326 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-1)/2)#define DEBUG/##/struct EDGE {int u, v, w ;bool operator< (const EDGE &e) {return w < e.w ;}};intn, m, edgeCnt ;intset[MAXN] ;intmap[MAXN][MAXN] ;EDGEedge[MAXE] ;void init_kruskal(){int i ;for (i = 1 ; i <= n ; ++i)set[i] = i ;edgeCnt = 0 ;}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 ;sort (edge, edge+m) ;sum = 0 ;// 没初始化，WAfor (i = 0 ; i < m ; ++i){if (n-1 <= edgeCnt) //这里的话，<= 和 == 在hdu结果是一样的break ;int x = find (edge[i].u) ;int y = find (edge[i].v) ;if (x != y){merge (x, y) ;++edgeCnt ;sum += edge[i].w ;}}return sum ;}int main (){int i, b ;while (scanf ("%d", &n), n){m = n*(n-1)/2 ;// 初始化，跟之前的模板题不同，这题要先初始化（个人的想法）init_kruskal() ;for (i = 0 ; i < m ; ++i){scanf ("%d%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w, &b) ;if (b) //对于已经建成的路，就检查是否在集合中{int x = find(edge[i].u) ;int y = find(edge[i].v) ;if (x != y) //若不在同一个集合，就合并集合{merge (x, y) ;++edgeCnt ; // 别忘了边数也要递增}--i, --m ; // 放到了 find(edge[i].u) 前面，WA}}printf ("%d\n", kruskal()) ;}return 0 ;}