评测记录

#4,5,6,7,9 WA

调了很久没有找到问题

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,k,i,cnt,tot=0;
double p[1100][2];
int fa[1100];

struct edge
{
	int u,v;
	double w;
} Edge[1000100];

int find(int x)
{
	if(x==fa[x])
	{
		return x;
	}
	return fa[x]=find(fa[x]);
}

bool cmp(edge a,edge b)
{
	return a.w<b.w;
}

int main()
{
	cin>>n>>k;
	for(i=1; i<=n; i++)
	{
		cin>>p[i][0]>>p[i][1];
		fa[i]=i;
		for(int j=1; j<i; j++)
		{
			int x=p[i][0]-p[j][0],y=p[i][1]-p[j][1];
			Edge[++tot].u=j;
			Edge[tot].v=i;
			Edge[tot].w=sqrt((double)(x*x+y*y));
		}
	}
	sort(Edge+1,Edge+tot+1,cmp);
//	for(i=1; i<=tot; i++)
//	{
//		printf("%d %d %lf\n",Edge[i].u,Edge[i].v,Edge[i].w);
//	}
	cnt=n,i=1;
	while(1)
	{
		if(cnt==k)
		{
			break;
		}
		int a=Edge[i].u,b=Edge[i].v;
		int a2=find(a),b2=find(b);
		if(a!=b)
		{
			cnt--;
			fa[a2]=b2;
//			cout<<a<<" "<<b<<endl;
//			for(int j=1; j<=n; j++)
//			{
//				cout<<find(j)<<" ";
//			}
//			cout<<endl;
		}
		i++;
	}
	while(find(Edge[i].u)==find(Edge[i].v))
	{
		i++;
	}
	printf("%.2lf",Edge[i].w);
	return 0;
}