P4047 部落划分 最小生成树

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const int Max=2e4;
struct Edge{
	int u,v;
	double w;
}edge[N];
struct Node{
	int x,y;
}node[N];
int cnt,fa[N];
int n,k;
double Dis(int a,int b){
	return sqrt((node[a].y-node[b].y)*(node[a].y-node[b].y)+
			    (node[a].x-node[b].x)*(node[a].x-node[b].x));
}
bool cmp(Edge a,Edge b){return a.w<b.w;}
int find(int a){
	if(fa[a]!=a) return fa[a]=find(fa[a]);
	return fa[a];
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)	scanf("%d%d",&node[i].x,&node[i].y),fa[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			edge[++cnt].u=i,edge[cnt].v=j,edge[cnt].w=Dis(i,j);			
		}
	sort(edge+1,edge+1+cnt,cmp);
//	for(int i=1;i<=cnt;i++){
//		printf("(%d,%d):%.2lf\n",edge[i].u,edge[i].v,edge[i].w);
//	}
	int u,v;
	bool flag=false;
	for(int i=1;i<=cnt;i++){
		u=edge[i].u,v=edge[i].v;
		if(find(u)!=find(v)){
			if(flag){
				printf("%.2lf\n",edge[i].w);
				break;
			}
			else{
				n--;
				fa[fa[v]]=find(u);
			}
		}
		if(n==k){
//			printf("QAQ %d\n",i);
//			printf("%.2lf %d",edge[i+1].w,i+1); 非部落间距 
			flag=true;
		}
	}
	return 0;
}