「Arctic Network」社交网络

形式化题目

严重注意：本题的原始题目描述与测试数据完全不符。 原始题面描述的是 ZJOI2007 的“社交网络”（计算最短路介数中心性）。但通过分析输入输出数据可知，测试数据的实际题意为经典的 POJ 2349 / AcWing 1145 “Arctic Network”。以下以测试数据的真实题意为准。

给定平面上的 $P$ 个点（前哨站）以及它们二维坐标 $(x, y)$ 。现要将这 $P$ 个点通过无线电网络连接起来，使得任意两点能够相互通信（可以直接通信，也可以通过其他点间接通信）。我们拥有 $S$ 个卫星通信频道。如果两个点都分配有卫星频道，那么它们可以无视距离直接通信；否则，它们之间必须通过无线电收发器通信，且两点之间的距离不能超过无线电收发器的通信半径 $D$ 。求当有 $S$ 个卫星频道时，通信半径 $D$ 的最小可能值。

输入格式 第一行包含一个整数 $T$ ，表示测试数据组数。对于每组数据：第一行包含两个整数 $S$ 和 $P$ ，分别表示卫星频道的数量和前哨站的数量。接下来 $P$ 行，每行包含两个整数 $x_i, y_i$ ，表示一个前哨站的坐标。

输出格式 对于每组测试数据，输出一个保留 $2$ 位小数的实数，表示最小的通信半径 $D$ 。

数据范围

$1 \le S \le 100$
$S < P \le 500$
$0 \le x_i, y_i \le 10000$

正解

思路

根据题意，我们可以将 $P$ 个前哨站看作完全图的 $P$ 个节点，图中任意两点之间的边权为其在平面上的欧几里得距离。 $S$ 个卫星频道可以将至多 $S$ 个连通块相互连接起来，且连通块之间不受通信半径 $D$ 限制。这就意味着我们需要用边长不超过 $D$ 的边将图连通为最多 $S$ 个连通块。根据 Kruskal 算法的性质：如果我们按边权从小到大加入边，初始有 $P$ 个连通块（每个点独立）。当连通块数量减少到 $S$ 个时，我们一共需要加入 $P-S$ 条有效边。为了使需要加入的最大边权最小，我们需要求的就是这个图的最小生成树中权值从小到大排序后的第 $P-S$ 条边的权值。

具体做法如下：

预处理出任意两点间的距离，总共 $\frac{P(P-1)}{2}$ 条边。
对所有边按照权值从小到大排序。
利用并查集进行 Kruskal 算法求最小生成树，直到加入了 $P-S$ 条边为止，最后加入的一条边的权值即为答案 $D$ 。如果 $P \le S$ ，则不需要建立任何无线电连接，答案为 $0.00$ 。

代码

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
60
61
62
63
64
65
66#!/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-10-09 13:44
# update_at: 2026-10-09 13:44

import sys
from math import sqrt

type Point = tuple[int, int]   # 前哨站坐标


def find_root(pa: list[int], x: int) -> int:
    """并查集找根，带路径压缩（写成迭代，避免深递归）。"""
    root = x
    while pa[root] != root:
        root = pa[root]
    while pa[x] != root:
        pa[x], x = root, pa[x]
    return root


def min_radius(s: int, p: int, pts: list[Point]) -> float:
    """通信半径最小值：完全图 MST 中第 P-S 小的边权（S 是卫星信道数）。"""
    edges: list[tuple[float, int, int]] = sorted(
        (sqrt((pts[i][0] - pts[j][0]) ** 2 + (pts[i][1] - pts[j][1]) ** 2), i, j)
        for i in range(p)
        for j in range(i + 1, p)
    )

    pa = list(range(p))
    need = p - s            # 连通块 1 个点降到 S 个，需要加入 P-S 条边
    if need <= 0:           # P <= S 时全部点用卫星直连，半径为 0
        return 0.0
    ans = 0.0
    added = 0
    for w, u, v in edges:
        ru, rv = find_root(pa, u), find_root(pa, v)
        if ru != rv:
            pa[ru] = rv
            ans = w             # 最后加入的这条边就是瓶颈边
            added += 1
            if added == need:
                break
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        t = next(data)
    except StopIteration:   # 空输入直接退出，不抛异常
        return

    out: list[str] = []
    for _ in range(t):
        s, p = next(data), next(data)
        pts: list[Point] = [(next(data), next(data)) for _ in range(p)]
        out.append(f"{min_radius(s, p, pts):.2f}")

    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

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
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * 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-10-09 13:44
 * update_at: 2026-10-09 13:44
 */
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll MAX_P = 505;    // 题面 P <= 500，多开几个留余量
const ll MAX_E = MAX_P * MAX_P / 2; // 完全图边数上界 P(P-1)/2

struct Point {
    ll x; // 前哨站横坐标
    ll y; // 前哨站纵坐标
};
Point pt[MAX_P];         // pt[i] 为第 i 个前哨站（0 基）

struct Edge {
    ll u;      // 边的一端
    ll v;      // 边的另一端
    double w;  // 两点的欧几里得距离
};
Edge edge[MAX_E];        // 完全图的所有边

ll edge_cnt;             // 完全图边数
ll pa[MAX_P];            // 并查集父亲

// 并查集找根（带路径压缩）
ll find_root(ll x) {
    if (pa[x] == x) return x;
    return pa[x] = find_root(pa[x]);
}

// 按边权升序排序用的比较函数
bool cmp_edge(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

// 每组数据：Kruskal 加到第 P-S 条边即为最小通信半径
void solve() {
    ll s, p;
    cin >> s >> p;
    for (ll i = 0; i < p; i++) {
        cin >> pt[i].x >> pt[i].y;
    }

    edge_cnt = 0;
    for (ll i = 0; i < p; i++) {
        for (ll j = i + 1; j < p; j++) {
            ll dx = pt[i].x - pt[j].x;
            ll dy = pt[i].y - pt[j].y;
            ll len2 = dx * dx + dy * dy; // 平方距离，直接用 ll 算避免精度损失
            edge[edge_cnt].u = i;
            edge[edge_cnt].v = j;
            edge[edge_cnt].w = sqrt(len2);
            edge_cnt++;
        }
    }
    sort(edge, edge + edge_cnt, cmp_edge);

    for (ll i = 0; i < p; i++) {
        pa[i] = i;
    }

    ll need = p - s;   // 连通块从 P 个降到 S 个，需要加入 P-S 条边
    double ans = 0.0;  // P <= S 时全部用卫星信道，半径为 0
    if (need > 0) {
        ll added = 0;
        for (ll i = 0; i < edge_cnt; i++) {
            ll ru = find_root(edge[i].u);
            ll rv = find_root(edge[i].v);
            if (ru != rv) {
                pa[ru] = rv;
                ans = edge[i].w; // 最后加入的这条边就是瓶颈
                added++;
                if (added == need) break;
            }
        }
    }
    cout << fixed << setprecision(2) << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    if (!(cin >> t)) return 0;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度

时间复杂度：
- 计算距离矩阵生成所有边需要 $O(P^2)$ 的时间。
- 对 $O(P^2)$ 条边排序需要 $O(P^2 \log P)$ 的时间。
- 并查集操作几乎是常数时间，最多遍历所有边，耗时 $O(P^2 \alpha(P))$ 。
- 总体时间复杂度为 $O(P^2 \log P)$ ，足以在给定数据范围下顺利通过。
空间复杂度： 需要存储 $O(P^2)$ 条边，空间复杂度为 $O(P^2)$ 。

总结

★★★ 题面 ≠ 数据：实测得出四条决定性的格式层面判据，证明真实数据完全不属于原始题面：
1. S1：题面要求第一行 n m（两个整数），但 1.in 第一行是 5，只有一个 token，格式不成立。
2. S2：按题面读边 a b c，在 n=5, m=1 解释下，第一条边解析为 2 0 0，b=0 越界且 c=0 违反 c≥1，数据按题面非法。
3. S3：题面要求“精确到小数点后 3 位”（如样例的 1.000），但 1.out 全部是 2 位小数（如 141.42）。
4. S4：题面要求输出 n 行，数据碰巧也是 5 行，但这其实是 5 个独立的测试用例（T=5）。 最强反向验证：如果严格按照原题面写 Floyd + 最短路计数，在题面的样例上能够正确输出 1.000 × 4；而在真实数据 1.in 上，一读入就因“非法边”直接崩溃。这完美证明了不是实现错误，而是数据本身就是另外一道题。
精确的输入解析规则：文件的第一行为组数 T（恰好 1 个 token，T=5）；随后循环 T 次：每次先读一行 S 和 P，然后再读 P 行坐标对 x y。按照该规则消费数据，全部 3023 个 token 消耗完 0 剩余。文件行数完美吻合结构不变量： $1 + \sum(1+P) = 1 + (1+2) + (1+4) + 3 \times (1+500) = 1512$ 行。
V7 算法指纹：并查集中的合并次数 unions 精确等于 P-S。这标志着实现本质就是 Kruskal（全局排序+并查集）；若是 Prim 则选点次数恒为 P-1，且全源最短路根本不使用并查集。
V8 数据的分辨力（与 3166/3120 的对比）：本题数据具有非常强的一致性和分辨力。针对“第几小”的不同候选：
- 取第 P-S 小：全数通过（0 错误）。
- 取第 P-S+1 小：5/5 全错。
- 取最大边（第 P-1 小）：在用例 1、3、4 出错。这三者的失败集互不相同，直接唯一确定了“第 P-S 小”的规则。相比于 3166（遍历顺序不可复现）和 3120（MIRROR 只到区间），本题的数据完全能反向推导出正确的逻辑。
V6 异源与自纠 Bug：三条独立路径（① 二分答案 $D$ + 连通块 $\le S$ ；② 朴素 Prim 求 MST 再排序；③ 主解 Kruskal）输出逐字节一致。在对拍 977 + 123 组小规模随机数据时，成功抓出了 Worker 在 Python 重写中遗漏 P<=S 守卫的真 Bug。

反事实表与数据盲区：

改动	结果	承重?
第 `P-S` 小 → `P-S+1`	FAIL 0/1（`594.00 420.10` 等）	✅
第 `P-S` 小 → 最大边	FAIL 0/1（`709.51 798.02`）	✅
第 `P-S` 小 → 第 1 条边	FAIL 0/1（`13.89 11.18 22.47`）	✅
去掉 `sqrt`	FAIL 0/1（`20000.00 …`）	✅
欧氏 → 曼哈顿	FAIL 0/1（`200.00 1005.00 …`）	✅
`%.2f` → `%.3f`	FAIL 0/1	✅
`%.2f` → `%.1f`	FAIL 0/1	✅
输入 `S P` 顺序交换	崩溃 rc=138	✅
去掉排序（用原顺序）	FAIL 0/1（`4644.16 …`）	✅
去掉 `if (need>0)` 守卫	1/1 PASS（1 点全 `S<P`）	⚠ 单点测不出
换成题面的 Floyd 图论算法	解析即失败（非法边）	✅ 证明题面算法不适用

单点未覆盖：去掉 need>0（即 P-S <= 0）守卫逻辑上是致命的，因为这会导致输出最后一条或者错乱的值（合成数据 S=100, P=2 在无守卫时输出 14142.14 而非 0.00）。但实际数据（1 点）的 5 个测试用例都不存在 $P \le S$ 的情况，因此该承重逻辑恰巧成了“数据盲区”。

V2/V4/V9/闸门对照组：
- V2 非硬编码：代码中无硬编码值，甚至数字部分都不出现。扫描到存在 sort() 以及配套的并查集 find_pa，印证是 Kruskal。
- V4 结构不变：完全消费 0 剩余，1512 行无误。本题输出结果纯粹由数字和小数点组成且为 LF 结尾，无 CRLF 缺陷。
- V9 UBSan 干净，且故意引入 -ftrapv INT_MIN 的对照组确实报错，探针有效，原程序无 UB。两组闸门规则均能有效捕获微小扰动与硬编码，保证不放过任何假绿灯。
T23/T24 不适用说明：本题计算距离 sqrt(dx*dx + dy*dy) 是单次平方和并开方，这其中没有 a*b+c 的连续模式，意味着浮点融合乘加 (FMA) 没有任何收缩空间。不论是 -O2、-O0 还是 -ffp-contract=off/fast，最终的运算结果绝对一致，浮点风险较低。
T9 浮点与异常规范：
- 浮点格式化：C++ fixed+setprecision(2)，Python f"{ans:.2f}"，高度一致。
- 极值守卫：特判 P <= S 防止输出非法边界值。

「Arctic Network」 社交网络

目录

形式化题目

正解

思路

代码

复杂度

总结

「Arctic Network」社交网络