首页 > ACM题库 > HDU-杭电 > HDU 1879 继续畅通工程-最小生成树-[解题报告] C++
2013
12-23

HDU 1879 继续畅通工程-最小生成树-[解题报告] C++

继续畅通工程

问题描述 :

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全省畅通需要的最低成本。

输入:

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。

当N为0时输入结束。

输出:

每个测试用例的输出占一行,输出全省畅通需要的最低成本。

样例输入:

3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0

样例输出:

3
1
0

/* 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: 
5317574	2012-02-05 14:27:17	Accepted	1879
187MS	212K	1827 B
C++	pyy

5317518	2012-02-05 14:19:53	Runtime Error
(ACCESS_VIOLATION)	1879
0MS	240K	1884 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)

#define DEBUG	/##/

int		n, m ;
int		used[MAXN], dist[MAXN] ;
int		map[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 ;
}

解题报告转自:http://blog.csdn.net/panyanyany/article/details/7234728


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮