求助,WA0分
查看原帖
求助,WA0分
413065
xiezheyuan楼主2022/1/27 09:20
#include<bits/stdc++.h>
using namespace std;

struct Edge{
	int u,v;double w;
	bool operator<(const Edge ed) const {
		return w<ed.w;
	}
}e[1000000];

int cnt;

void add(int uu,int vv,double ww) {
	e[++cnt].u=uu;
	e[cnt].v=vv;
	e[cnt].w=ww;
}

int x[10005],y[10005],fa[10005];
int n,k,l;

inline double d(int x1,int y1,int x2,int y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int find(int u){
	if(fa[u]==u){
		return u;
	}
	else{
		return fa[u]=find(fa[u]);
	}
}
bool merge(int u,int v){
	int fu=find(u);
	int fv=find(v);
	if(fu==fv)return false;
	else{
		fa[fu]=fv;
		return true;
	}
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			double ld=d(x[i],x[j],y[i],y[j]);
			add(i,j,ld);
		}
	}
	sort(e+1,e+1+cnt);
	for(int i=1;i<=cnt;i++){
		bool flag=merge(e[i].u,e[i].v);
		if(!flag){
			continue;
		}
		l++;
		if(l==n-k+1){
			printf("%.2lf",e[i].w);
			break;
		}
	}
	return 0;
}

2022/1/27 09:20
加载中...