【最小生成树+Prim】杭电 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 : Sunday, February 05, 2012 Time Stage : half an hour Result: 53175742012-02-05 14:27:17Accepted1879187MS212K1827 BC++pyy53175182012-02-05 14:19:53Runtime Error(ACCESS_VIOLATION)18790MS240K1884 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/##/intn, m ;intused[MAXN], dist[MAXN] ;intmap[MAXN][MAXN] ;int Prim (){int i, j, iMinPath, MinPath, sum ;MEM (used, 0) ;for (i = 1 ; i <= n ; ++i)dist[i] = map[1][i] ;//dist[0] = INF ;used[1] = true ;sum = 0 ;// 一开始的时候是 i<=n ，结果 sum 一直都大于 INF，因为多运行的那一次// 已经没有路可走了，所以 MinPath 就为 INF ，sum 于是就糊里糊涂地加上了……for (i = 1 ; i <= n-1 ; ++i){MinPath = INF ;for (j = 1 ; j <= n ; ++j)if (!used[j] && dist[j] < MinPath){MinPath = dist[j] ;iMinPath = j ;}used[iMinPath] = true ;sum += MinPath ;for (j = 1 ; j <= n ; ++j)if (!used[j] && dist[j] > map[iMinPath][j])dist[j] = map[iMinPath][j] ;}return sum ;}int main (){int i ;int x, y, c, b ;while (scanf ("%d", &n), n){MEM (map, INF) ;m = n*(n-1)/2 ;for (i = 1 ; i <= m ; ++i){scanf ("%d%d%d%d", &x, &y, &c, &b) ;if (b)c = 0 ;map[x][y] = map[y][x] = min(map[x][y], c) ;}printf ("%d\n", Prim()) ;}return 0 ;}