题解 | #北极通讯网络#

#include <bits/stdc++.h>
 
using namespace std;
 
typedef double ld;

typedef pair <int,int> PII;
 
const int N = 201000;
 
int n,k,idx; 
int p[N];
PII q[N];

ld get(int x1,int y1,int x2,int y2)
{
	int dx=x1-x2;
	int dy=y1-y2;
	return sqrt(dx*dx+dy*dy);
}

struct Node
{
    int x,y;
    double z;
}st[N];
 
bool cmp(Node a,Node b)
{
    return a.z<b.z;
}
 
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
 
void Kruskal()
{
    ld res=0;
	int cnt=n;
 
    for(int i=1;i<=idx;i++)
    {
        int a=st[i].x,b=st[i].y;
		ld c=st[i].z;
 
        a=find(a),b=find(b);
 
        if(a!=b)
        {
            p[a]=b;
            res=c;
            cnt--;
            if(cnt<=k) break;
        }
    }
    printf("%.2lf",res);
}
 
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) p[i]=i;
 	for(int i=1;i<=n;i++) cin>>q[i].first>>q[i].second;

    for(int i=1;i<=n;i++)
    	for(int j=1;j<=i;j++)
    		st[++idx]={i,j,get(q[i].first,q[i].second,q[j].first,q[j].second)};
 
    sort(st+1,st+idx+1,cmp);
 
    Kruskal();

    return 0;
}