无线通讯网

GitHub跳转原题关系图返回列表

把卫星电话理解为允许保留 S 个无线连通块，在完全图上 Kruskal 到剩 S 个集合。

OJ: luogu

题目 ID: P1991

难度:普及/提高-

标签:最小生成树Kruskal并查集几何聚类

日期: 2026-06-22 21:54

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 P 个哨所，其中可以给 S 个哨所配卫星电话。任意两个有卫星电话的哨所可以无视距离通信。

普通无线电的通信距离统一为 D。要求选择尽量小的 D，使所有哨所最终都能直接或间接连通。

思路

先看一个可以直接验证想法的朴素解：

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

// brute.cpp：枚举小数据的卫星分块划分，验证最小 D。

const int MAXP = 12;

int s, p;
int x_pos[MAXP], y_pos[MAXP];
int group_id[MAXP];
double answer;

double distance_between(int i, int j) {
    double dx = x_pos[i] - x_pos[j];
    double dy = y_pos[i] - y_pos[j];
    return sqrt(dx * dx + dy * dy);
}

void read_input() {
    cin >> s >> p;
    for (int i = 1; i <= p; i++) {
        cin >> x_pos[i] >> y_pos[i];
    }
}

void evaluate() {
    double need = 0.0;
    for (int g = 1; g <= s; g++) {
        vector<int> nodes;
        for (int i = 1; i <= p; i++) {
            if (group_id[i] == g) {
                nodes.push_back(i);
            }
        }
        if ((int)nodes.size() <= 1) {
            continue;
        }

        bool used[MAXP];
        double dist[MAXP];
        for (int i = 0; i < (int)nodes.size(); i++) {
            used[i] = false;
            dist[i] = 1e100;
        }
        dist[0] = 0.0;

        for (int step = 0; step < (int)nodes.size(); step++) {
            int u = -1;
            for (int i = 0; i < (int)nodes.size(); i++) {
                if (!used[i] && (u == -1 || dist[i] < dist[u])) {
                    u = i;
                }
            }
            used[u] = true;
            need = max(need, dist[u]);

            for (int v = 0; v < (int)nodes.size(); v++) {
                if (!used[v]) {
                    double w = distance_between(nodes[u], nodes[v]);
                    if (w < dist[v]) {
                        dist[v] = w;
                    }
                }
            }
        }
    }

    answer = min(answer, need);
}

void dfs(int pos, int used_groups) {
    if (pos == p + 1) {
        if (used_groups == s) {
            evaluate();
        }
        return;
    }

    for (int g = 1; g <= used_groups; g++) {
        group_id[pos] = g;
        dfs(pos + 1, used_groups);
    }

    if (used_groups < s) {
        group_id[pos] = used_groups + 1;
        dfs(pos + 1, used_groups + 1);
    }
}

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

    read_input();
    answer = 1e100;
    group_id[1] = 1;
    dfs(2, 1);

    cout << fixed << setprecision(2) << answer << '\n';

    return 0;
}

如果没有卫星电话，所有哨所必须靠无线电连成一张图，答案就是最小生成树中的最大边。

现在有 S 个卫星电话，可以把最多 S 个无线连通块用卫星连接起来。所以问题变成：用无线电把所有点连成 S 个连通块，并让块内需要的最大边尽量小。

这就是 Kruskal 聚类：

  1. 枚举所有哨所点对，边权为欧氏距离；
  2. 按距离从小到大排序；
  3. 用并查集合并不同连通块；
  4. 当连通块数量降到 S 时停止；
  5. 最后一次加入的边长，就是最小通信距离 D。

也可以理解为：先建完整 MST，再删掉最大的 S-1 条边。剩下每个连通块内部靠无线电，块与块之间靠卫星电话。

代码

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

const int MAXP = 505;
const int MAXE = 130000;

struct Edge {
    int u, v;
    double w;
};

int s, p;
int x_pos[MAXP], y_pos[MAXP];
Edge edge[MAXE];
int edge_count;
int father[MAXP];

bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

int find_root(int x) {
    if (father[x] == x) {
        return x;
    }
    father[x] = find_root(father[x]);
    return father[x];
}

bool merge_set(int x, int y) {
    int rx = find_root(x);
    int ry = find_root(y);
    if (rx == ry) {
        return false;
    }
    father[rx] = ry;
    return true;
}

double distance_between(int i, int j) {
    double dx = x_pos[i] - x_pos[j];
    double dy = y_pos[i] - y_pos[j];
    return sqrt(dx * dx + dy * dy);
}

void read_input() {
    cin >> s >> p;
    for (int i = 1; i <= p; i++) {
        cin >> x_pos[i] >> y_pos[i];
    }
}

void build_edges() {
    edge_count = 0;
    for (int i = 1; i <= p; i++) {
        for (int j = i + 1; j <= p; j++) {
            edge_count++;
            edge[edge_count].u = i;
            edge[edge_count].v = j;
            edge[edge_count].w = distance_between(i, j);
        }
    }
}

void solve() {
    build_edges();
    sort(edge + 1, edge + edge_count + 1, cmp_edge);

    for (int i = 1; i <= p; i++) {
        father[i] = i;
    }

    int components = p;
    double answer = 0.0;
    for (int i = 1; i <= edge_count && components > s; i++) {
        if (merge_set(edge[i].u, edge[i].v)) {
            answer = edge[i].w;
            components--;
        }
    }

    cout << fixed << setprecision(2) << answer << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

完全图有 O(P2)O(P^2) 条边，排序复杂度为 O(P2logP)O(P^2 log P)。

空间复杂度为 O(P2)O(P^2)。

总结

卫星电话的作用不是改变边权，而是允许最终保留多个无线连通块。

因此 Kruskal 不必做到全图连通，只要合并到剩下 S 个连通块即可。