2009-1.18-pku1861.txt

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

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXV=1005;
const int MAXE=501000;
int set[MAXV];
int rank[MAXV];
int num;
typedef struct Edge
{
	int st;
	int ed;
	int distance;
}Edge;
Edge edge[MAXE];
Edge edge1[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,max=-1;
	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中去
			if(edge[i].distance>max)
				max=edge[i].distance;
			Union(edge[i].st,edge[i].ed);//并将包含这两棵树的集合合并
			edge1[++num]=edge[i];
		}
	return max;
}
/*求最小生成树的Kruskal算法 按照<<算法导论>>自己写了一个模板!*/
int main()
{
	int V,E,i,max,row,col,distance;
	while(scanf("%d%d",&V,&E)!=EOF)
	{
		num=0;
		for(i=1;i<=E;i++)
		{
			scanf("%d%d%d",&row,&col,&distance);
			edge[i].st=row<col? row:col;//保证每条边的起点是最小值
			edge[i].ed=row<col? col:row;//保证每条边的终点是最大值
			edge[i].distance=distance;
		}
		max=Kruskal(V,E);
		printf("%d\n",max);
		printf("%d\n",num);
		for(i=1;i<=num;i++)
			printf("%d %d\n",edge1[i].st,edge1[i].ed);
	}
	return 0;
}
/*
原来是本着最小生成树的练习去做这道题目的。但是看了却发现：有些顶点之间没有边相连。。。
想了一分钟，哦，设为无穷大就可以了。然后看样例输出：咦？4 个顶点的“最小生成树”竟然有4条边？？？
难道这道题目是搜索？还有special judge???细细想三分钟，不对呀，边权为正的话要是整个图连通的最优方案一定是n-1条边的呀
（如果有n-1+k(k为正）的话，一定有环，把环中多的边删掉就会更优，矛盾）。。。怎么会？难道样例有错？？？
 再一看，原来最小生成树只是解题方法的一种，题目没有要求你算出最小生成树只要求输出可以连通的方案中最长的边，
 这个边的权值必须最少，那么直接把最小生成树中最长的边输出来就可以了，样例的输出可不是最小生成树。。。样例没错。
 如果那个最长的边不在最小生成树中，由于最长的边权值要最小，这就意味着有一条不在最小生成树中的，
 连接a,b两点的边比最小生成树中连接a,b的边要小，这样子就与"最小"矛盾。
 <<所以这一题只用输出最小生成树中的最长边权值和每一条边即>>。

4 6
1 2 1
1 3 1
1 4 2
2 3 1
3 4 1
2 4 1

1
4
1 2
1 3
2 3
3 4
*/