Solution

\(Kruskal\) 加一点点东西就好...

\(n\) 很小,可以暴力搞出所有的边.

然后按照边的大小排序. 用一个并查集维护关系.

同时记录联通块的数量,大于 \(k\) 的时候照样维护关系.

如果已经等于 \(k\) ,直接找到第一条两端点不在同一联通块的边输出就好.

Code

#include
    
     #define db doubleusing namespace std;const int maxn=1008;struct sj{  int to,fr; db w;}a[maxn*maxn];int fa[maxn],num[maxn];int n,k,cnt,pp;db x[maxn],y[maxn],ans;int read(){    char ch=getchar(); int f=1,w=0;    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}    return f*w;}bool cmp(sj x,sj y){return x.w
     
      num[y])swap(x,y);    if(x!=y)fa[x]=y;    num[y]+=num[x]; num[x]=0;}int main(){    n=read(); k=read(); pp=n;    for(int i=1;i<=n;i++)        x[i]=db(read()),y[i]=db(read()),fa[i]=i;    for(int i=1;i<=n;i++)        for(int j=i+1;j<=n;j++)        {          a[++cnt].fr=i,a[cnt].to=j;          a[cnt].w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));        }        sort(a+1,a+cnt+1,cmp);    for(int i=1;i<=cnt;i++)        {          int x=a[i].fr,y=a[i].to;          if(pp>k)          {            if(find(x)!=find(y))            {join(x,y);pp--;}          }          else            if(find(x)!=find(y))              {printf("%.2lf\n",a[i].w);break;}        }    return 0;}