luoguP4047[JSOI2010]部落划分

神奇的最小生成树题😀

n^2枚举每一个点，计算出每两点之间的距离
因为没合并一次，就会减少一个部落，所以我们需要合并n-k次
根据贪心的思想，每次我们需要挑出距离最近的两个点合并，否则答案就会变小
所以我们预先排个序，然后每次从小到大找没有连接起来的点，合并即可
是不是特别像kruskal
所以直接跑kruskal模板，找出n-k条边即可，最后输出下一条没有合并的边权，也就是最小距离

#include <bits/stdc++.h>
#include<cstdio>
using namespace std;
int n,m;
int x[1001000],y[1000100];
struct edge{
    int a,b;
    double c;
}e[2001000];
double dis(int x,int y,int x1,int y1){
    return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}
bool cmp(edge a,edge b){
    return a.c<b.c;
}
int fa[1001000];
int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        fa[i]=i;
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            e[++cnt].a=i;
            e[cnt].b=j;
            e[cnt].c=dis(x[i],y[i],x[j],y[j]);
        }
    }
    sort(e+1,e+cnt+1,cmp);
    int tot=0;
    for(int i=1;i<=cnt;i++){
        //cout<<e[i].a<<" "<<e[i].b<<" "<<e[i].c<<endl;
        int A=get(e[i].a),B=get(e[i].b);
        if(A!=B){
            tot++;
            fa[A]=B;
        }
        if(tot==n-m+1){
            printf("%.2lf",e[i].c);            
            return 0;
        }
    }
    return 0;
}