jsoi 部落划分

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
struct ppp {
    int x,y,v;
} a[500005];
bool cmp(ppp a,ppp b) {
    return a.v<b.v;
}
int f[1005],x[1005],y[1005],tot,n,k,xx,yy;
int get(int x) {
    return f[x]==x?x:f[x]=get(f[x]);
}
int main() {
    scanf("%d%d",&n,&k);
    for (int i=1; i<=n; i++) scanf("%d%d",&x[i],&y[i]);
    for (int i=1; i<=n; i++)
        for (int j=i+1; j<=n; j++) 
		{
            tot++;
            a[tot].x=i;
            a[tot].y=j;
            a[tot].v=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
        }
    sort(a+1,a+tot+1,cmp);//将边权从小到大排序 
    
    for (int i=1; i<=n; i++) 
	    f[i]=i;
    for (int i=1; i<=tot; i++) 
	//取出边来，尽量让小边所连的点，放在同一个部落中 
	{
        xx=get(a[i].x);
        yy=get(a[i].y);
        if (xx!=yy) 
		//最开始N个点分成N个集合，如果不在一个集合，则合并起来 
		//集合个数减少一个 
		{
            n--;
            f[xx]=yy;
            if (n<k) 
			//这里理解清楚，当集合个数小于k时，则说明当前已分成了K个集合了
			//当前的边就是答案了 
			{
                printf("%.2lf",sqrt(a[i].v));
                return 0;
            }
        }
    }
}