图论训练之十

https://www.luogu.org/problem/P4047

好久没做生成树的题目了，这个算复习一下吧

我们把每个点看成一个部落，每次取最小距离的两个抱团，同时部落也减少了一个....然后减减减，直到部落数==目标数，此时下一个不同部落的距离就是最短的距离

code

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
const int MA = 1e7;
using namespace std;
int o,n,k,num,flag;
int fa[MA];
inline int read()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))c = getchar();
    while(c>='0'&&c<='9')
    {
        x = x*10+c-'0';
        c = getchar();
    }
    return x;
}
struct s
{
    int x,y;double l;
}ass[MA],e[MA];
double cmp(s x,s y)
{   return x.l < y.l;}
int find(int a)
{
    if(fa[a]!=a)
        fa[a] = find(fa[a]);
    return fa[a];
}
void unionn(int a,int b)
{   fa[find(b)] = find(a); }
void kruskal()
{
    for(int i=1;i<=o;i++)
    {
        if(num==n-k) flag = 1;
        if(find(e[i].x)!=find(e[i].y))
        {
            num++;
            unionn(e[i].x,e[i].y);
        if(flag){
            printf("%.2lf",e[i].l);
            return ;
            }
        }
    }
}
double measure(int a,int b{return sqrt(pow((ass[a].x-ass[b].x),2)+pow((ass[a].y-ass[b].y),2));}
int main()
{
    n = read(),k = read();
    for(int i=1;i<=n;i++)
        ass[i].x = read(),ass[i].y = read();
    o = 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(i!=j)e[++o].x=i,e[o].y=j,e[o].l=measure(i,j);
    for(int i=1;i<=n;i++)
        fa[i] = i;
    sort(e+1,e+1+o,cmp);
    kruskal();
    return 0;
}