#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int per[260000],n,m;
double a[260000];
struct node
{
	int x,y;
	double w;
}s[260000];
bool cmp(node x,node y)
{
	return x.w<y.w;
}
void init()
{
	for(int i=0;i<=n;i++)
	per[i]=i;
}
int find(int x)
{
	int i,j,t=x;
	while(t!=per[t])
	t=per[t];
	i=x;
	while(i!=t)
	{
		j=per[i];
		per[i]=t;
		i=j;
	}
	return t;
}

bool join(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
		per[fx]=fy;
		return true ;
	}
	return false;
}
int main()
{
	int i,j,n1;
	scanf("%d",&n1);
	while(n1--)
	{
		double x[600],y[600];
		scanf("%d%d",&m,&n);
		init();
		for(i=0;i<n;i++)
			scanf("%lf%lf",&x[i],&y[i]);
			int k=0;
			for(i=0;i<n;i++)
			{
				for(j=i+1;j<n;j++)
				{
					s[k].x=i;
					s[k].y=j;
					s[k++].w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
				}
			}
			sort(s,s+k,cmp);
			int t=0;
			for(int i=0 ; i<k ;  i++)
			{
				if(join(s[i].x,s[i].y))
				a[t++]=s[i].w;
			}
			printf("%.2f\n",a[t-m]);
	}
	return 0;
}

• Re:最小生成树水过~~~~~~~~~~~~~~~~ (1271) LeibnizZhang 2016-02-21 15:54:51
• 超时一百年，求大神帮解决 (1566) LXY5201314 2017-12-16 21:58:06