43 · 最小生成树与并查集

把卫星电话翻译成连通块数。S 台卫星电话各自装在一个连通块里，块与块之间靠卫星通信，块内部必须靠无线电连通。所以最终恰好允许剩下 S 个连通块。分成更少块就浪费了电话，分成更多块则有一块没有电话、无法与外界通信。

问题变成：把 P 个点分成 S 块，使每块内部连通所需的无线电距离尽可能小，并对所有块取最大值。这正是“最小化最大边”的瓶颈问题，交给 MST。

Kruskal 恰好是一个不断减少连通块的过程。初始 P 块，每加入一条不成环的边，块数减 1。块数从 P 减到 S 需要 P − S 次合并，第 P − S 条被加入的边的长度就是答案——因为它正是“让块数刚好降到 S”的那道坎。

为什么不是第 P − S + 1 条？第 P − S 条加入后块数已经是 S，此时可以收手了；再加一条就把块数压到 S − 1，等于浪费了一台卫星电话，而那条边只会更长。

边界：S ≥ P 时每台哨所都能装卫星电话，不需要任何无线电，d = 0。不特判会让“凑够 P − S 条”永远不成立，ans 被更新到最大边。

复杂度。边数 P(P−1)/2 ≤ 124750，排序约 1.2×10⁵ × 17 ≈ 2×10⁶ 次比较，并查集十余万次操作，几十毫秒。

等价写法。也可以二分 d，判定“只用长度 ≤ d 的边能否把图连成 ≤ S 块”，复杂度 O(P² log)，能过但多一个 log，而 Kruskal 一次就做完了。

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

const int MAXP = 505, MAXE = MAXP * MAXP;   // 完全图最多 P(P-1)/2 条边

struct Edge { int u, v; double w; } e[MAXE];
int fa[MAXP], sz[MAXP];
double x[MAXP], y[MAXP];

int find(int a) { return fa[a] == a ? a : fa[a] = find(fa[a]); }

bool merge(int a, int b) {                  // 返回 true 表示这次真的合并了两块
    a = find(a); b = find(b);
    if (a == b) return false;               // 已连通，这条边会成环
    if (sz[a] < sz[b]) swap(a, b);
    fa[b] = a; sz[a] += sz[b];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int S, P;
    cin >> S >> P;
    for (int i = 1; i <= P; ++i) cin >> x[i] >> y[i];

    if (S >= P) {                           // 每台都装卫星电话，不需要无线电
        cout << fixed << setprecision(2) << 0.0 << "\n";
        return 0;
    }

    int m = 0;
    for (int i = 1; i <= P; ++i)            // 建完全图：任意两点都可能用无线电通信
        for (int j = i + 1; j <= P; ++j) {  // 从 i+1 开始，避免自环与重复边
            double dx = x[i] - x[j], dy = y[i] - y[j];
            e[++m] = {i, j, sqrt(dx * dx + dy * dy)};
        }

    sort(e + 1, e + m + 1, [](const Edge &a, const Edge &b) { return a.w < b.w; });

    for (int i = 1; i <= P; ++i) { fa[i] = i; sz[i] = 1; }

    int need = P - S;                       // 从 P 块压到 S 块，需要 P-S 次合并
    int got = 0;
    double ans = 0;
    for (int i = 1; i <= m; ++i) {
        if (!merge(e[i].u, e[i].v)) continue;   // 成环，跳过
        ans = e[i].w;                       // 记下这次合并用的边长
        if (++got == need) break;           // 凑够 P-S 条就停
    }

    cout << fixed << setprecision(2) << ans << "\n";
    return 0;
}