kruskal求解

问题需要转化一下思路，转化为找一个权值, 当去掉权值的边后, 剩余的连通块的数量要.

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

const int N=505; // NC上本题数据范围缺失, 从LOJ上查询到1<=n<=500, 0<=k<=100
int n, k;
int fa[N], posx[N], posy[N];

struct Edge{int x, y; double d;};
vector<Edge> e;

inline bool cmp(const Edge &e1, const Edge &e2){return e1.d<e2.d;}
inline double dist(int x1, int y1, int x2, int y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

double kruskal(){
    int i=0;
    sort(e.begin(), e.end(), cmp);
    for(auto &edge: e){
        int x=edge.x;
        int y=edge.y;
        if(find(x)!=find(y)){
            fa[find(x)]=find(fa[y]);
            if(++i==n-k) return edge.d;
        }
    }
    return -1;
}

int main(){
    cin>>n>>k;
    if(k>=n) {cout<<0.00<<endl; return 0;}
    for(int i=1; i<=n; ++i){fa[i]=i; cin>>posx[i]>>posy[i];}
    for(int i=1; i<=n; ++i)
        for(int j=i+1; j<=n; ++j)
            e.push_back({i, j, dist(posx[i], posy[i], posx[j], posy[j])});
    cout<<fixed<<setprecision(2)<<kruskal()<<endl;
    return 0;
}