hdu 题目1233 还是畅通工程（Prime算法）

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 20006 Accepted Submission(s): 8874

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input

Sample Output

3
5

最小生成树——Prim和Kruskal算法

先从其它网站上转载了点算法：

这里讨论的是无向图的最小生成树，有向图的最小生成树算法比较复杂，如果感兴趣可以参看清华大学的《信息学奥林

匹克竞赛指导－图论的算法与程序设计》。

所谓最小生成树，就是给定一个无向图，挑选若干条边，连成一个树行图（无圈），使得所选边的权至和最小。

一下算法中，n是点数，e是边数。

1.Prim

初始时任选一点s为树根，每次选出一条权最小的边[i,j]，使得点i在树中，点j不在树中，将j和[i,j]加入树中，重复n-1次

求出最小生成树。

我们用二叉堆来提高效率。二叉堆中存储边，初始时二叉堆中存储与s关联的边，每次取出一个权最小的边[i,j]，删除

[i,j]，同时将与j关联的边放入二叉堆中，注意判重。

因为所有边只放入和取出二叉堆一次，所以算法复杂度是(eloge)。

2.Kruskal

从所有边中找到一个最小的边，且将改变放入后不会生成圈，重复n-1次后求出最小生成树。

我们首先将所有边排序，然后从小到大判断，如果不产生圈就加入树中，当加入n-1条边时停止。

为了判断是否组成圈，我们要用到并查集，相关知识可以在本站或任一本竞赛书中找到，这里不赘述。

算法复杂度是(eloge+eα)，α是做一次并查集的复杂度，可以认为是常数。

两种算法同样优秀。

/*
	2013/08/04 11:03
	author : zyh
*/

#define N  101
#include <iostream>
#include <stdio.h>

using namespace std;

int city[N][N],road[N];//road 存放当前集合所包含的顶点
bool visit[N];

int sum,n;

void Min(int count) 
{
	
 	int i,j,last,m;
	m = 999999;
 	for(i=1; i<=count; i++)//在road的顶点内所连接的边寻找最小边
 	{	
 		for(j=1;j<=n;j++)
		{
	 		if(!visit[j] &&  m>city[road[i]][j]  && city[road[i]][j] != 0)
	 		{
	 			last = j;// 标记最小边和 下标
				m = city[road[i]][j];
	 		}	
		} 
 	}
 //	printf("min=%d,index=%d\n",m,last);
	sum += m;
	road[++count] = last;
	visit[last] = 1;
}

void Prim()
{
	int i;	
	for(i=1;i<=n;i++) visit[i] = 0;
	road[1] = 1;//从第一个城市开始 
	int count = 1;
	visit[1] = 1;
	while(count<n)
	{
		Min(count);
		count++;
	}
}

int main()
{
	int i,j,a,b,c;
	while(scanf("%d",&n),n)
	{
		for(i=1;i<= n*(n-1)/2;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			city[a][b] = city[b][a] = c; 
		}
//		for(i=1;i<=n;i++)
//		{
//			for(j=1;j<=n;j++)
//			printf("%d ",city[i][j]);
//				printf("\n");
//		}		
		sum = 0;
		Prim();
		printf("%d\n",sum);
	}
	return 0;
}