【最小生成树+Prim】杭电 hdu 1233 还是畅通工程

第一次 Prim 思想初步实践版

/* 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  : Sunday, February 5, 2012
    Time Stage : one hour

    Result: 
5316885	2012-02-05 11:43:47	Accepted	1233
203MS	212K	1639 B
C++	pyy

5316784	2012-02-05 11:19:20	Wrong Answer	1233
93MS	212K	1655 B
C++	pyy


Test Data :

Review :
这个程序的耗时比较大，因为是我根据 Prim 算法的思想自己写的代码，最原始，也是最慢的。
它每次都要遍历两个集合中的每个元素，并且外面还有一个大循环，总共便是接近O(n^3)的耗时。
//----------------------------------------------------------------------------*/

#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] ;
int		map[MAXN][MAXN] ;

int Prim ()
{
	int i, j, sum, MinPath, iMinPath, nCnt ;

	MEM(used, 0) ;

	used[1] = true ;
	nCnt = 0 ;
	sum = 0 ;

	q[nCnt++] = 1 ;

	while (nCnt < n)
	{
		int end = nCnt ;
		MinPath = INF ;	// 一开始这个放到第一个for里面去了，结果WA
		// 遍历集合，找出到剩余各点的最短路径
		for (j = 0 ; j < end ; ++j)
		{
			int t = q[j] ;
			for (i = 1 ; i <= n ; ++i)
			{
				if (!used[i] && map[t][i] < MinPath)
				{
					MinPath = map[t][i] ;
					iMinPath = i ;
				}
			}
		}
		if (INF > MinPath)	// 一开始这个放到第一个for里面去了，结果WA
		{
			used[iMinPath] = true ;
			q[nCnt++] = iMinPath ;
			sum += MinPath ;
		}
	}
	return sum ;
}

int main ()
{
	int i ;
	int x, y, c ;
	while (scanf ("%d", &n), n)
	{
		MEM(map, INF) ;
		m = n*(n-1)/2 ;
		for (i = 1 ; i <= m ; ++i)
		{
			scanf ("%d%d%d", &x, &y, &c) ;
			map[x][y] = map[y][x] = min(c, map[x][y]) ;
		}
		printf ("%d\n", Prim ()) ;
	}
	return 0 ;
}

第一次 Prim 参考解题报告版

/* 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  : Sunday, February 5, 2012
    Time Stage : one hour

    Result: 
5316958	2012-02-05 12:02:07	Accepted	1233
93MS	212K	1757 B
C++	pyy


Test Data :

Review :
此程序的思想是，先建立一个数组保存从 集合1 到 集合2 的最短距离。
一开始，集合1的点是 1，集合2的点是除1以外的点。然后一次 for 循环保存从
点1 到其他各点的距离。……详情见注释
//----------------------------------------------------------------------------*/

#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, sum, MinPath, iMinPath ;

	MEM(used, 0) ;
	sum = 0 ;

	// 保存 1 点到其他点的距离
	for (i = 1 ; i <= n ; ++i)
		dist[i] = map[1][i] ;
	used[1] = true ;		// 标记此点已经在集合1中

	for (j = 1 ; j <= n - 1 ; ++j)
	{
		// 求出集合1 到其他各点的距离的最小值
		MinPath = INF ;
		for (i = 1 ; i <= n ; ++i)
		{
			if (!used[i] && dist[i] < MinPath)
			{
				MinPath = dist[i] ;
				iMinPath = i ;
			}
		}
		// 标记此点已经加入到集合1中
		used[iMinPath] = true ;
		sum += dist[iMinPath] ;

		// 加入 iMinPath 点后，更新集合到其他点的距离
		for (i = 1 ; i <= n ; ++i)
		{
			if (!used[i] && dist[i] > map[iMinPath][i])
				dist[i] = map[iMinPath][i] ;
		}
	}
	return sum ;
}

int main ()
{
	int i ;
	int x, y, c ;
	while (scanf ("%d", &n), n)
	{
		MEM(map, INF) ;
		m = n*(n-1)/2 ;
		for (i = 1 ; i <= m ; ++i)
		{
			scanf ("%d%d%d", &x, &y, &c) ;
			map[x][y] = map[y][x] = min(c, map[x][y]) ;
		}
		printf ("%d\n", Prim ()) ;
	}
	return 0 ;
}