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

题目描述

$n$ 座村庄坐标已知，任意两村可用距离不超过 $d$ 的无线电直接通讯，另有 $k$ 台卫星设备可配给任意村庄（卫星直连无距离限制）。求保证所有村庄连通的最小 $d$ ，保留两位小数。

思路

$k$ 台卫星设备等价于把村庄分成至多 $\max(k,1)$ 个连通块、块间用卫星免费互联，问题转化为求最小生成树后删去最大的 $\max(k-1,0)$ 条边，剩余最大边权即为答案； $k \ge n$ 时答案为 0。用 Kruskal 求出生成树各边权，升序取倒数第 $\max(k,1)$ 大即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-10-04 11:46
import math
import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)  # 空输入按原样直接返回
    if n is None:
        return
    k = next(data)
    pts = [(next(data), next(data)) for _ in range(n)]  # n 行坐标，按题面顺序 (x, y) 成对消费

    if k >= n:
        print("0.00")
        return

    # 生成所有点对的无向边并按欧氏距离升序排序
    edges = sorted(
        (math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1]), i, j)
        for i in range(n)
        for j in range(i + 1, n)
    )

    parent = list(range(n))

    def find(x: int) -> int:
        curr = x
        while parent[curr] != curr:
            curr = parent[curr]
        while parent[x] != curr:
            parent[x], x = curr, parent[x]
        return curr

    # Kruskal 算法求生成树，记录加入生成树的所有边权
    tree_weights: list[float] = []
    for w, u, v in edges:
        fu, fv = find(u), find(v)
        if fu != fv:
            parent[fu] = fv
            tree_weights.append(w)
            if len(tree_weights) == n - 1:
                break

    # k 台卫星设备可以使最多 k 个连通块各自内部连通或两两连通
    # 相当于消去生成树中权值最大的 max(k - 1, 0) 条边
    # 剩下的最大边权即为所求的无线电通讯距离 d
    remove_count = max(k - 1, 0)
    ans = tree_weights[-(remove_count + 1)] if remove_count < len(tree_weights) else 0.0
    print(f"{ans:.2f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87// 北极通讯网络（一本通 3.1 例 2）
// Kruskal 最小生成树：k 台卫星设备相当于把树中最大的 max(k-1,0) 条边
// 用卫星链路替代，剩下的最大边权就是无线电收发机需要的最小 d。
#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 505;
const int MAXE = MAXN * MAXN / 2;

typedef long long ll;

int n, k;
int x[MAXN], y[MAXN];
int fa[MAXN];

struct Edge {
    double w; // 边权（欧氏距离）
    int u, v; // 端点
};

Edge eg[MAXE]; // 全部点对的边
int ecnt;      // 边数

// 边权升序比较（供 sort 使用，不用 lambda）
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

// 并查集：查找根
int find(int a) {
    while (fa[a] != a) {
        fa[a] = fa[fa[a]]; // 路径压缩
        a = fa[a];
    }
    return a;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &x[i], &y[i]);

    // 卫星设备足够时 d 可以为 0
    if (k >= n) {
        printf("0.00\n");
        return 0;
    }

    // 构造全部点对的边
    ecnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            double dx = x[i] - x[j];
            double dy = y[i] - y[j];
            eg[++ecnt].w = sqrt(dx * dx + dy * dy);
            eg[ecnt].u = i;
            eg[ecnt].v = j;
        }

    // 按边权升序排序（Kruskal）
    std::sort(eg + 1, eg + ecnt + 1, cmp_edge);

    for (int i = 1; i <= n; i++)
        fa[i] = i;

    // 生成树的边权从小到大依次存入 tw
    double tw[MAXN]; // 生成树各边权值
    int tcnt = 0;
    for (int i = 1; i <= ecnt && tcnt < n - 1; i++) {
        int fu = find(eg[i].u);
        int fv = find(eg[i].v);
        if (fu != fv) {
            fa[fu] = fv;
            tw[++tcnt] = eg[i].w;
        }
    }

    // 去掉最大的 max(k-1,0) 条边后，剩余最大边即答案
    int remove_cnt = k - 1;
    if (remove_cnt < 0) remove_cnt = 0;
    double ans = 0.0;
    if (remove_cnt < tcnt)
        ans = tw[tcnt - remove_cnt];
    printf("%.2f\n", ans);
    return 0;
}

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

目录

题目描述

思路

参考代码