`

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

阅读更多

/* 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  : Monday, February 06, 2012
    Time Stage : half an hour

    Result: 
5320358	2012-02-06 09:30:05	Accepted	1233
125MS	244K	1671 B
C++	pyy


Test Data :

Review :
还是Prim算法快啊!
//----------------------------------------------------------------------------*/

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

struct EDGE {
	int u, v, w ;
	bool operator< (const EDGE &e) {
		return w < e.w ;
	}
};

int		n, m ;
int		used[MAXN], set[MAXN] ;
int		map[MAXN][MAXN] ;

EDGE	edge[MAXE] ;

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, edgeCnt ;
	sort (edge, edge+m) ;

	// 并查集初始化,每个独立集的根结点都是自己
	for (i = 1 ; i <= n ; ++i)
		set[i] = i ;

	sum = edgeCnt = 0 ;
	for (i = 0 ; i < m ; ++i)
	{
		// 查找 u 和 v 所在集合的根结点
		int x = find(edge[i].u) ;
		int y = find(edge[i].v) ;

		// 若根结点不同,表示存在两个独立的集合,则合并之~
		if (x != y)
		{
			// 合并操作
			merge (x, y) ;
			// 合并则意味着新边的加入
			sum += edge[i].w ;
			// 边数加1
			++edgeCnt ;
			// 若边数满足条件,则表示所有的点都合并到一个集合中了,可以退出了
			if (n-1 == edgeCnt)
				break ;
		}
	}
	return sum ;
}

int main ()
{
	int i ;
	while (scanf ("%d", &n), n)
	{
		m = n*(n-1)/2 ;
		for (i = 0 ; i < m ; ++i)
			scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w) ;
		printf ("%d\n", kruskal()) ;
	}
	return 0 ;
}

0
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics