如题,调了两个小时了,球球路过的谷友帮帮忙吧 qwq。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1005;
const int MAXM=500005;
int n,k;
int f[MAXN],x[MAXN],y[MAXN];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
struct edge{int u,v;int w;} e[MAXM];
bool cmp(edge a,edge b){return a.w<b.w;}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
int m=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<n;j++){
int dx=x[i]-x[j],dy=y[i]-y[j];
int d=dx*dx+dy*dy;
e[++m].u=i;e[m].v=j,e[m].w=d;
}
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++)f[i]=i;
int cnt=n,i=1;
for(i;i<=m&&cnt>k;i++){
int u=find(e[i].u),v=find(e[i].v);
if(u!=v) f[u]=v,cnt--;
}
double ans=0.0;
for(i;i<=m;i++){
int u=find(e[i].u),v=find(e[i].v);
if(u!=v){
ans=sqrt((double)e[i].w);
cout<<fixed<<setprecision(2)<<ans<<endl;
return 0;
}
}
}