`

【最小生成树+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: 
5317462	2012-02-05 14:07:12	Accepted	1863
0MS	212K	1820 B
C++	pyy

5317444	2012-02-05 14:04:25	Wrong Answer	1863
0MS	212K	1761 B
C++	pyy


Test 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	/##/

int		n, m ;
int		used[MAXN], q[MAXN], dist[MAXN] ;
int		map[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 初始化为 1
			break ;			// 继续循环下去会改变 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 ("?") ;
		else
			printf ("%d\n", ans) ;
	}
	return 0 ;
}
0
1
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics