【最小生成树+kruskal】杭电 hdu 1879 持续畅通工程
【最小生成树+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: 5320539 2012-02-06 10:34:06 Accepted 1879 281MS 236K 2326 B C++ pyy Test 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 ; } }; int n, m, edgeCnt ; int set[MAXN] ; int map[MAXN][MAXN] ; EDGE edge[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 ; // 没初始化,WA for (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 ; }