「一本通 1.2 练习 2」扩散

形式化题目

平面上给定 $n$ 个点（ $1 \leqslant n \leqslant 50$ ，坐标为 $1 \sim 10^9$ 的整数）。每个点从时刻 $0$ 起向四个方向扩散，时刻 $t$ 时覆盖所有到该点曼哈顿距离 $\leqslant t$ 的格子（一个菱形）。若点 $a$ 、 $b$ 的扩散区域在时刻 $t$ 有公共格子，则它们在时刻 $t$ 连通。求最早的时刻 $T$ ，使所有点在时刻 $T$ 构成一个连通块。

正解

思路

第一步：两点何时连通？

时刻 $t$ ，点 $a$ 的扩散区域是所有满足 $|x-a_x|+|y-a_y| \leqslant t$ 的格子（一个对角线方向的菱形）。两个菱形有公共格子，等价于存在点 $(x,y)$ 同时满足两个不等式，两式相加得

|x-a_x|+|y-a_y|+|x-b_x|+|y-b_y| \leqslant 2t,

左边由三角不等式放缩到下界 $|a_x-b_x|+|a_y-b_y|$ ，即两点曼哈顿距离 $d(a,b)$ ；并且当 $(x,y)$ 取在 $a$ 、 $b$ 连线（折线）上时该下界可以取到。所以

a,b \text{ 在时刻 } t \text{ 连通} \iff d(a,b) \leqslant 2t \iff t \geqslant \left\lceil \frac{d(a,b)}{2} \right\rceil.

第二步：连通的时刻转化为图。

把每个点看作图上的一个顶点，给每对点连一条无向边，边权为 $w(a,b)=\lceil d(a,b)/2 \rceil$ ，表示这条边「被接通」的最早时刻。

在时刻 $T$ ，原图中所有 $w \leqslant T$ 的边都已接通，所有点形成连通块当且仅当这些边构成连通图，即 $T$ 至少要覆盖一棵生成树的所有边。为了让 $T$ 最小，应选边权最大值最小的生成树——最小生成树（MST）。

\text{答案} = \text{MST 的最大边权}.

样例验证：两点 $(0,0)$ 与 $(5,5)$ ， $d=10$ ，答案 $\lceil 10/2\rceil = 5$ ，与样例一致。

实现： $n \leqslant 50$ ，是完全图上的稠密图，用 Prim 即可，每轮选离生成树最近的点并入，过程中维护已选边权的最大值，最后输出。

代码

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#!/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 14:47
# 题目: roj 1437 扩散
# 结论: 时刻 t 两菱形(切比雪夫转曼哈顿菱形)相交 <=> 曼哈顿距离 <= 2t
#       边权 w = ceil(dist/2), 答案 = 最小生成树的最大边权
# 复杂度: O(n^2) 建完全图, Prim 求最小生成树, n<=50
import sys

data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
P = [(next(data), next(data)) for _ in range(n)]  # 每行一个点的坐标 (x, y)
if n == 1:
    print(0)  # 只有一个点, 时刻 0 即连通
    raise SystemExit

a, b = P[0]
d = [abs(a - c) + abs(b - e) for c, e in P]  # Prim 初始: 点 0 到各点的距离
used, ans = [False] * n, 0
for _ in range(n):  # 做 n 轮, 每轮选出离生成树最近的点
    k = min(range(n), key=lambda i: (used[i], d[i]))  # 未使用的里挑最近的
    used[k], ans = True, max(ans, d[k])  # 并入生成树, 更新树的最大边
    d = [min(d[i], abs(P[i][0] - P[k][0]) + abs(P[i][1] - P[k][1])) if not used[i] else d[i]
         for i in range(n)]  # 用新点 k 松弛其余点
print(-(-ans // 2))  # ceil(ans/2): 边权 d 的扩散时刻

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/**
 * 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-05 01:08
 * update_at: 2026-10-05 01:08
 */
// roj 1437 扩散
// 结论: 时刻 t 两个扩散菱形(曼哈顿距离意义)相交 <=> 曼哈顿距离 <= 2t
//       于是把边权看作两点曼哈顿距离, 答案 = 最小生成树最大边权的一半向上取整
// 做法: 完全图稠密, n<=50, 用 O(n^2) 的 Prim 求最小生成树
#include <cstdio>
using namespace std;
typedef long long ll;

const int MAXN = 55;
ll px[MAXN]; // 第 i 个点的横坐标
ll py[MAXN]; // 第 i 个点的纵坐标
ll min_dist[MAXN]; // min_dist[i] = 第 i 个点到当前生成树的最小曼哈顿距离
bool used[MAXN]; // used[i] = 点 i 是否已经并入生成树

ll abs_ll(ll v) {
    if (v < 0) {
        return -v;
    }
    return v;
}

// 两点曼哈顿距离
ll manhattan(int i, int j) {
    return abs_ll(px[i] - px[j]) + abs_ll(py[i] - py[j]);
}

int main() {
    ll n;
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld%lld", &px[i], &py[i]);
    }

    // Prim: 先把点 1 放入生成树, 其余点的距离初始为到点 1 的曼哈顿距离
    for (ll i = 1; i <= n; i++) {
        min_dist[i] = manhattan(1, i);
    }
    used[1] = true;

    ll max_edge = 0; // 生成树中最大的边权(曼哈顿距离形式)
    for (ll round = 1; round <= n - 1; round++) {
        // 在未使用的点里找离生成树最近的点
        ll best = 0;
        for (ll i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            if (best == 0 || min_dist[i] < min_dist[best]) {
                best = i;
            }
        }
        used[best] = true;
        if (min_dist[best] > max_edge) {
            max_edge = min_dist[best];
        }
        // 用新并入的点 best 松弛其余未使用的点
        for (ll i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            ll d = manhattan(i, best);
            if (d < min_dist[i]) {
                min_dist[i] = d;
            }
        }
    }

    // 边权为曼哈顿距离 d, 对应扩散时刻为 ceil(d/2)
    ll ans = (max_edge + 1) / 2;
    printf("%lld\n", ans);
    return 0;
}

复杂度

建边隐式在距离计算中：Prim 共 $n$ 轮，每轮 $O(n)$ 更新距离，总时间 $O(n^2)$ （完全图边数本身 $O(n^2)$ ，与 Kruskal 排序的 $O(n^2\log n)$ 同阶或更优）。
空间 $O(n)$ （只存每个点到生成树的最短距离，不需要显式存边）。

总结

扩散区域是曼哈顿距离意义下的菱形，两菱形相交 $\iff$ 两点曼哈顿距离 $\leqslant 2t$ 。
「所有点连通的最小时刻」= 完全图（边权 $\lceil d/2\rceil$ ）上最小生成树的最大边权，这是经典的「瓶颈生成树」转化。
稠密图 Prim $O(n^2)$ 恰好匹配 $n \leqslant 50$ 的规模。

图示解析

两个时刻 $t$ 各自扩散出的菱形（曼哈顿距离 $\leqslant t$ ），当二者接触/相交时即连通：

flowchart LR
    subgraph T1["t = 2: 菱形相距尚远, 未连通"]
        A1["点 a 的菱形<br/>半径 2"]
        B1["点 b 的菱形<br/>半径 2"]
        A1 -. "d=10 &gt; 2t=4" .-> B1
    end
    subgraph T2["t = 5: 菱形相切, 首次连通"]
        A2["点 a 的菱形<br/>半径 5"]
        B2["点 b 的菱形<br/>半径 5"]
        A2 == "d=10 &lt;= 2t=10" ==> B2
    end

多点情形下，每个点向其余点连边权为 $\lceil d/2 \rceil$ 的边，取最小生成树，其最大边权（瓶颈边）即为答案：

flowchart TD
    A["点 0 (0,0)"] -- "ceil(10/2)=5" --- B["点 1 (5,5)"]
    A -- "ceil(3/2)=2" --- C["点 2 (1,2)"]
    C -- "ceil(7/2)=4" --- B

上图中 MST 取边 $A\!-\!C(2)$ 与 $C\!-\!B(4)$ ，最大边权 $4$ ，即所有点连通的最早时刻为 $4$ 。