2009-2-21pku2349.txt

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

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXV=505;
const int MAXE=127275;
int set[MAXV];
int rank[MAXV];
typedef struct Point
{
	double x;
	double y;
}Point;
Point p[MAXV];
double a[MAXV];
typedef struct Edge
{
	int st;//边的起点
	int ed;//边的终点
	double 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,num=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;
			a[++num]=edge[i].distance;
			//并将包含这两棵树的集合合并
			Union(edge[i].st,edge[i].ed);
		}
	return num;
}
double Dis(Point a,Point b)
{
	double dis;
	dis=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
	return sqrt(dis);
}
bool cmp1(double a,double b)
{
	return a>b;
}
int main()
{
	int T,n,i,j,V,E,S;
	scanf("%d",&T);
	while(T--)
	{
		E=0;
		scanf("%d%d",&S,&V);
		for(i=1;i<=V;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		for(i=1;i<=V-1;i++)
			for(j=i+1;j<=V;j++)
			{
				edge[++E].st=i;
				edge[E].ed=j;
				edge[E].distance=Dis(p[i],p[j]);
			}
		n=Kruskal(V,E);
		sort(a+1,a+n+1,cmp1);
		//for(i=1;i<=n;i++)
			printf("%.2lf\n",a[S]);
	}
	return 0;
}
/*

1
2 4
0 100
0 300
0 600
150 750

212.13
有卫星电台的城市之间可以任意联络。
没有卫星电台的城市只能和距离小于等于D的城市联络。
题目告诉你卫星电台的个数S，让你求最小的D.
做最小生成树，去掉最长的S条边后，剩下最长的边就是D.
也就是求最小生成树中第S+1长的边。
完毕。
*/