Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/lp1991/

题意

题目传送门

给出若干点，定义距离小于 $D$ 的点可以归于一个集合，可以强行将 $S$ 个点归于一个集合，求所有点在同一个集合时 $D$ 的最小值。

解法

主流的题解都是使用最小生成树的解法。
但笔者是从并查集题单来的，而且习惯用 prim 写最小生成树，因此就打了个并查集的做法。
正确性应该更好证明、更好思考。

要求某值最小，常规套路是二分。
考虑二分 $D$ 的值，但距离值是浮点数，无法使用常规整数域二分。
可以预处理出所有点间的距离，去重排序后生成一个 $D$ 的数组，二分数组的下标。

在确认 $D$ 的情况下，考虑如何检验。
显然两点距离小于 $D$ 的可以归于一个集合，用并查集来处理。
若处理后只剩下一个集合，则合法。
若处理后剩余多个集合，考虑在两个集合之间增加卫星电话，这样该两个集合也并为一个。
那么消耗卫星电话数量即为集合数。(起点、终点都需要设置卫星电话)

检验的复杂度是 $O(n^2)$ 的，总复杂度为 $O(n^2 \log n)$，可以通过。

代码

代码实现也非常简单，就是一个二分板子套上一个并查集板子。

#include <cstdio>
#include <cmath>
#include <algorithm>
template <typename T>
void read(T &r)
{
    static char c;
    for (c = getchar(); c > '9' || c < '0'; c = getchar());
    for (; c >= '0' && c <= '9'; r = (r << 1) + (r << 3) + (c ^ 48), c = getchar());
}
const int maxp = 510;
int s, p;
int X[maxp], Y[maxp];
double dis[maxp][maxp];
double D[maxp * maxp];
int tot;
int fa[maxp];
int find(const int &x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void unite(const int &a, const int &b)
{
    int x = find(a), y = find(b);
    if (x == y)
        return;
    fa[x] = y;
}
inline bool check(double d)
{
    for (int i = 1; i <= p; ++i)
        fa[i] = i;
    for (int i = 1; i <= p; ++i)
        for (int j = i + 1; j <= p; ++j)
            if (dis[i][j] <= d)
                unite(i, j);
    int num = 0;
    for (int i = 1; i <= p; ++i)
        if (find(i) == i)
            ++num;
    if (num == 1)
        return true;
    return tree <= s;
}
int main()
{
    read(s);
    read(p);
    for (int i = 1; i <= p; ++i)
        read(X[i]), read(Y[i]);
    for (int i = 1; i <= p; ++i)
        for (int j = i + 1; j <= p; ++j)
            dis[i][j] = dis[j][i] = std::sqrt((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j])), D[++tot] = dis[i][j];
    std::sort(D + 1, D + 1 + tot);
    tot = std::unique(D + 1, D + 1 + tot) - D;
    int l = 1, r = tot, mid, ans;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (check(D[mid]))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    printf("%.2f", D[ans]);
    return 0;
}