10065. 「一本通 3.1 例 2」北极通讯网络

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

const int N = 500005;
int fa[N], n, k, ind;
double x[N], y[N];
void init() {
    for (int i = 0; i <= n; i++) fa[i] = i;
}
int find(int p) { return (p == fa[p]) ? (p) : (fa[p] = find(fa[p])); }
void merge(int p, int q) {
    p = find(p);
    q = find(q);
    fa[p] = q;
}
double dist(double x1, double y1, double x2, double y2) {
    return sqrt(pow((x2 - x1), 2) + pow((y2 - y1), 2));
}
struct Edge {
    int u, v;
    double w;
    bool operator<(const Edge &b) { return w < b.w; }
} e[N];
double ans = 0;
int cnt = 0;

int main() {
    // ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            Edge tmp;
            tmp.u = i;
            tmp.v = j;
            tmp.w = dist(x[i], y[i], x[j], y[j]);
            e[++ind] = tmp;
        }
    }
    sort(e + 1, e + ind + 1);
    init();
    for (int i = 1; i <= ind; i++)
        if (find(e[i].u) != find(e[i].v)) {
            merge(e[i].u, e[i].v);
            ++cnt;
            if (cnt + k <= n)
                ans = max(ans, e[i].w);
        }
    cout << setiosflags(ios::fixed) << setprecision(2) << ans << endl;
}#include <bits/stdc