1914.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;

struct line
{
	int e,b;
	double d;
};
const int MAXN=600;
int x[MAXN],y[MAXN];
line p[250010];
int u[MAXN];
bool cmp(line a,line b)
{
	if(a.d<b.d)return true;
	else
		return false;
}
int findhead(int h)
{
	if(u[h]==h)return h;
	else
	{
		u[h]=findhead(u[h]);
		return u[h];
	}
}

int main()
{
	int i,j,k,l;
	int T,t;
	scanf("%d",&T);
	int s,n;int a,b;
	for(t=1;t<=T;t++)
	{
		scanf("%d%d",&s,&n);
		for(i=1;i<=n;i++)
		{
			
			scanf("%d%d",&x[i],&y[i]);
		}
		int c=0;
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
			{
				c++;
				p[c].b=i;
				p[c].e=j;
				p[c].d=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);
			}
		sort(&p[1],&p[c+1],cmp);
		for(i=1;i<=n;i++)
			u[i]=i;
		int edge=0;
		for(k=1;k<=c;k++)
		{
			int ha,hb;
			a=p[k].b;b=p[k].e;
			ha=findhead(a);hb=findhead(b);
			if(ha==hb)continue;
			edge++;
			u[hb]=ha;
			if(edge==n-s)break;
		}
		printf("%.2lf\n",sqrt(p[k].d));
	}
	return 0;
}