LibreOJ #10065 北极通讯网络（转化题意，巧用最小生成树）

题目链接：https://loj.ac/problem/10065


题意转化：已知卫星设备的数量，求最小的收发距离，可能比较困难。如果知道距离，求数量就简单。
问题转化：找到一个最小的d，使得把所有权值大于d的边去掉之后，连通支的个数小于等于k。
定理：如果去掉所有权值大于d的边后，最小生成树被分割成为k个连通分支，则图也被分割成k个连通支。
基于题意和上述定理：最小生成树的第k长边就是问题的解。
证明：
d取最小生成树中的第k长的边是可行的。如果d取第k长的边，我们将去掉最小生成树中前k-1长的边，最小生成树将被分割为k部分。
其次，如果d比最小生成树中的第k长的边小的话，最小生成树至少被分割为k+1部分，与题意不符。
综上所述：最小生成树的第k长的边总是使连通支的个数小于等于k的最小的d。
代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;/*构造最小生成树*/
const int N=510;
int f[N],tx[N],ty[N];
int n,K;
struct node
{
    int x,y;
    double z;
} s[N*N];
double solve(int x1,int y1,int x2,int y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int cmp(node xx,node yy)
{
    return xx.z<yy.z;
}
int getf(int d)
{
    if(d==f[d])
        return f[d];
    else
    {
        f[d]=getf(f[d]);
        return f[d];
    }
}
int gether(int bx,int by)
{
    int t1=getf(bx);
    int t2=getf(by);
    if(t1!=t2)
    {
        f[t1]=t2;
        return 1;
    }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&K);
    if(K>=n)/*可以保证每个村庄都用卫星*/
    {
        printf("0.00\n");
        return 0;
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&tx[i],&ty[i]);
        f[i]=i;
    }
    int k=0;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)/*构造图*/
            s[++k]=(node){i,j,solve(tx[i],ty[i],tx[j],ty[j])};
    sort(s+1,s+k+1,cmp);
    int cot=0;
    int ans=0;
    double sum[N];
    memset(sum,0,sizeof(sum));
    for(int i=1; i<=k; i++)
    {
        if(gether(s[i].x,s[i].y))
        {
            cot++;
            sum[++ans]=s[i].z;
        }
        if(cot==k-1)
            break;
    }
    printf("%.2lf\n",sum[ans-K+1]);
    return 0;
}