全WA求条
查看原帖
全WA求条
1379071
LOVE_WHY楼主2025/6/15 11:11
#include <bits/stdc++.h>
using namespace std;
int n,k,fa[501],tx[1001],ty[1001];
struct node{
	int st,en;
    double quan;
}p[500001];
bool cmp(node x,node y){
	return x.quan<y.quan;
}
int find(int x){
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
double load(int x,int y,int xx,int yy){
    return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
int main(){
	cin>>n>>k;
    int cnt=1;
	for (int i=1;i<=n;++i){
		fa[i]=i;
		cin>>tx[i]>>ty[i];
        for (int j=1;j<i;++j){
            p[cnt].st=j,p[cnt].en=i;
            p[cnt].quan=load(tx[i],tx[j],ty[i],ty[j]);
            cnt++;
        }
	}
	sort(p+1,p+cnt+1,cmp);
    int cnt2=1;
	for (int i=1;i<=cnt;++i){
		int fx=find(p[i].st),fy=find(p[i].en);
		if (fx!=fy){
			fa[fx]=fy;
			if (cnt2==(n-k+1)){
                printf("%.2f",p[i].quan);
                break;
            }
            cnt2++;
		}
	}
	return 0;
} 
2025/6/15 11:11
加载中...