2009-1.17-pku1258.txt

MST算法就是最小生成树算法！ 在ACM中这个应该是比较简单的一个算法！ 大家好好学习吧！

/*自己的模板!*/
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX=105;
int set[MAX];
int rank[MAX];
typedef struct Edge
{
	int st;//边的起点
	int ed;//边的终点
	int distance;//边的权值
}Edge;
Edge edge[MAX*55];
int Dis[MAX][MAX];
/*下面三个函数是求并查集的函数!*/
//第一函数是初始化
void Make_Set(int x)
{
	set[x]=x;
	rank[x]=0;
}
//返回包含x的集合中的一个代表元素
int Find_Set(int x)
{
	if(x!=set[x])
		set[x]=Find_Set(set[x]);
	return set[x];
}
//实现树与树的合并
void Union(int x,int y)
{
	x=Find_Set(x);
	y=Find_Set(y);
	if(rank[x]>rank[y])
		set[y]=x;
	else
	{
		set[x]=y;
		if(rank[x]==rank[y])
			rank[y]++;
	}
}
bool cmp(Edge a,Edge b)
{
	return a.distance<b.distance;
}
/*关键函数-Kruskal算法的实现!*/
int Kruskal(int n)
{
	int i,sum=0;
	for(i=1;i<=n;i++)
		Make_Set(i);//每个点构成一个树也即一个集合
	sort(edge+1,edge+n+1,cmp);//将边按照权值非降序排序
	for(i=1;i<=n;i++)
		if(Find_Set(edge[i].st)!=Find_Set(edge[i].ed))
		{//如果是安全边就加sum中去
			sum+=edge[i].distance;
		 //并将包含这两棵树的集合合并
			Union(edge[i].st,edge[i].ed);
		}
	return sum;
}
/*求最小生成树的Kruskal算法 按照<<算法导论>>自己写了一个模板!*/
int main()
{
	int i,j,n,num,sum;
	while(scanf("%d",&n)!=EOF)
	{
		num=0;
		for(i=1;i<=n;i++)
		  for(j=1;j<=n;j++)
			  scanf("%d",&Dis[i][j]);
		//这两个循环也很重要！
		//读入所有边的权值，起点和终点！
		for(i=1;i<=n-1;i++)
			for(j=i+1;j<=n;j++)
			{
				edge[++num].st=i;
				edge[num].ed=j;
				edge[num].distance=Dis[i][j];
			}
		sum=Kruskal(num);
		printf("%d\n",sum);
	}
	return 0;
}
/*
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

28
*/