洛谷P1991 无线通讯网 题解 并查集+二分答案

题目链接：https://www.luogu.com.cn/problem/P1991

解题思路：

二分答案+并查集。

但是这道题目写的不是很明确，其实如果对于一个D大家都在一个连通块的时候，是不需要配备卫星通话线路的。

也就是说，如果我连通块的数量是 (cnt) ，那么我只需要判断 (cnt-1 le S) 是否成立即可。

但是这道题目好像至少需要一个，所以变成了判断 (cnt le S) 是否成立，就过了。

但是我感觉题目还是有些歧义。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int s, n;
double x[maxn], y[maxn];
int f[maxn];
void init() {
    for (int i = 1; i <= n; i ++) f[i] = i;
}
int Find(int x) {
    return x == f[x] ? x : f[x] = Find(f[x]);
}
void Union(int x, int y) {
    int a = Find(x), b = Find(y);
    f[a] = f[b] = f[x] = f[y] = min(a, b);
}
bool vis[maxn];
bool check(double D) {
    init();
    for (int i = 1; i <= n; i ++) {
        for (int j = i+1; j <= n; j ++) {
            if ((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) <= D*D) Union(i, j);
        }
    }
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for (int i = 1; i <= n; i ++) if (!vis[Find(i)]) { vis[Find(i)] = true; cnt ++; }
    return cnt <= s;
}
int main() {
    cin >> s >> n;
    for (int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
    double L = 0, R = 15000;
    while (R-L >= 1e-3) {
        double mid = (L + R) / 2.0;
        if (check(mid)) R = mid;
        else L = mid;
    }
    printf("%.2lf
", L);
    return 0;
}