2009-pku2377.txt

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

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MAXV=1005;
const int MAXE=100005;
int set[MAXV];
int rank[MAXV];
int use[MAXV];
typedef struct Edge
{
	int st;
	int ed;
	int distance;
}Edge;
Edge edge[MAXE];
/*下面三个函数是求并查集的函数!*/
//第一函数是初始化
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 v,int e)
{
	int i,sum=0;
	for(i=1;i<=v;i++)
		Make_Set(i);//每个点构成一个树也即一个集合
	sort(edge+1,edge+e+1,cmp);//将边按照权值降序排序，因为是求最大生成树
	for(i=1;i<=e;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;
}

/*判断是不是所有的点都联通了！*/
bool Judge(int v)
{
	int i;
	for(i=1;i<=v-1;i++)
		if(Find_Set(i)!=Find_Set(i+1))
			return false;
		return true;
}
int main()
{
	int i,V,E,sum;
	int st,ed,distance;
	while(scanf("%d%d",&V,&E)!=EOF)
	{
		for(i=1;i<=E;i++)
		{
			scanf("%d%d%d",&st,&ed,&distance);
			edge[i].st=st;
			edge[i].ed=ed;
			edge[i].distance=distance;
		}
		sum=Kruskal(V,E);
		if(Judge(V))
			printf("%d\n",sum);
		else
			printf("-1\n");
	}
	return 0;
}	
/*
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17


42
*/