[NOIP 2013 提高组] 货车运输

形式化题目

给定无向带权图 $G=(V,E)$ ， $n$ 个点、 $m$ 条边，边权 $w(e)$ 表示道路限重（ $0 \le z \le 10^5$ ，可能有重边）。一条路径 $P$ 能承载的货物重量是它最窄的那条边：

\text{load}(P) = \min_{e \in P} w(e)

有 $q$ 次询问，每次给两点 $x,y$ ，求

\text{ans}(x,y) = \max_{P:\, x \to y} \ \min_{e \in P} w(e)

即所有 $x \to y$ 路径中「路径最小边权」的最大值。若 $x,y$ 不连通，输出 $-1$ 。

数据范围： $n < 10^4$ ， $m < 5\times10^4$ ， $q < 3\times10^4$ 。

为什么与最短路无关

第一反应可能是「跑一遍最短路」。但最短路最小化的是边权之和：

\text{dist}(x,y) = \min_{P} \sum_{e \in P} w(e)

而本题要最大化的是路径上的最小边权。两个目标会选出完全不同的路径：一条边数少、总和小的路径可能中途夹着一条限重 1 的窄桥，而一条绕远路却条条边都限重 $10^5$ 的路径反而能运更重的货。样例里 $1 \to 3$ 直达要过限重 1 的边，绕道 $1 \to 2 \to 3$ 的最小边权是 3，才是答案。所以 Dijkstra / Floyd 这类「加法最短路」的框架在这里不适用——把转移从「求和取最小」改成「取 min 再取最大」才是对的方向，那正是瓶颈路（maximin path）问题。

核心性质：最大生成树路径上的最小边权 = 点对最大瓶颈值

这是本题唯一的难点。断言：设 $T$ 是 $G$ 的任意一棵最大生成树（注意按 Kruskal 从大到小加边得到的是最大生成森林，每个连通块内是一棵最大生成树），则

\forall x,y \text{ 同块}: \quad \min_{e \in P_T(x,y)} w(e) = \max_{P:\,x \to y} \min_{e \in P} w(e)

其中 $P_T(x,y)$ 是树上 $x$ 到 $y$ 的唯一路径。

证明。 记右边（原图最大瓶颈值）为 $B(x,y)$ 。

先证「 $\ge$ 」：树上路径也是原图的一条路径，所以 $B(x,y) \ge \min_{e \in P_T(x,y)} w(e)$ 。反着说更清楚——记 $W_T = \min_{e \in P_T(x,y)} w(e)$ ，则树上路径是一条全程限重 $\ge W_T$ 的可行路径，故 $B(x,y) \ge W_T$ 。

再证「 $\le$ 」，用 Kruskal 的阈值语言。想象按边权从大到小依次放开边（这正是建最大生成森林的过程）。设 $W$ 是让 $x,y$ 连通的最高阈值：只用权 $\ge W$ 的边时 $x,y$ 恰好（刚）连通，只用权 $> W$ 的边时还不连通。那么：

只用权 $\ge W$ 的边已能连通 $x,y$ ，所以存在一条全程限重 $\ge W$ 的路径， $B(x,y) \ge W$ ；
只用权 $> W$ 的边不能连通 $x,y$ ，所以任何 $x \to y$ 路径必含一条权 $\le W$ 的边， $B(x,y) \le W$ 。

两边夹住： $B(x,y) = W$ 。而 Kruskal 结束时 $x,y$ 同处一棵树，树上路径全部由已加入的边组成（权全 $\ge W$ ），且 $x,y$ 首次连通的时刻落在这棵树的形成过程中，两端到 LCA 的两段里必有一段含那条促成首次连通的权恰为 $W$ 的关键边，于是 $W_T = W = B(x,y)$ 。 $\blacksquare$

这个论证和 P1396 的「阈值连通性」是同一个骨架，只是方向翻过来了：P1396 问「让两点连通的最小阈值」（minimax），本题问「让两点连通的最大阈值」（maximin）。

为什么是最大生成树而不是最小生成树

因为阈值的方向反了。本题的有效边是「权大的边」——限重越大越好。把上面的证明按「权 $\ge W$ 」叙述，对应的 Kruskal 必须从大边开始加；如果从大边开始加的是最小生成树（从小边开始），阈值就变成「只用权 $\le W$ 的边」，论证出来的量是「路径最大边权的最小值」，与本题要求的量正好是相反的极端。

一个具体的反例：三点 $1,2,3$ ，边 $(1,2,w=4)$ 、 $(2,3,w=3)$ 、 $(1,3,w=1)$ 。最小生成树会选权 1 和权 3 的两条边，路径 $1 \to 3$ 的最小边权是 1；但正确答案是 3（走 $1 \to 2 \to 3$ ）。方向选反，答案直接错。

图不连通：建最大生成森林

题面不保证图连通（样例里 $1$ 到 $4$ 就无路可达），而生成树只在单个连通块内存在。解法是把 Kruskal 从大边跑完整个边表：每条边要么连接两个不同集合、进入森林，要么两端已同块、被丢弃。跑完后得到的是最大生成森林——每个连通块一棵最大生成树。

关键的一点是正确性不损失：上文证明里的阈值论证是在 $x,y$ 所在连通块内部自洽的，与别的块无关。若询问的两点分属不同块，原图中根本不存在 $x \to y$ 路径，直接输出 $-1$ 。实现上在 BFS 每个连通块时记一个 component[x] 块编号，查询时先比对块号， $O(1)$ 判掉跨块询问。

倍增 LCA 上如何维护路径最小边权

树建好后，每次询问就是在树上找 $x \to y$ 路径的最小边权。路径是 $x \to \text{LCA} \to y$ 两段拼起来的，所以问题化为「一个点向上跳若干条边，这段路上的最小边权」。

倍增表除了常规的 up[x][j]（向上跳 $2^j$ 条边到的祖先），再带一张 min_edge[x][j]（这 $2^j$ 条边里的最小权）。转移是

\text{up}[x][j] = \text{up}[\text{up}[x][j-1]][j-1]

\text{min\_edge}[x][j] = \min\big(\text{min\_edge}[x][j-1],\ \text{min\_edge}[\text{up}[x][j-1]][j-1]\big)

即「前一半的最小」和「后一半的最小」拼起来，因为取 min 满足结合律， $2^j$ 的段可以任意二进制拆分。递推顺序上用 BFS 按层填表：一个点出队时，它 $2^{j-1}$ 级祖先的表必然已填好（祖先的深度严格更小、更早入队）。根的 min_edge[root][0] 填 $+\infty$ （根没有父边），不影响取 min。

查询分三步，每步沿途用 min_edge 更新答案：

拉齐深度。 设 $d(x) \ge d(y)$ ，把 $x$ 向上跳 $d(x)-d(y)$ 条边。把差值按二进制拆分，第 $j$ 位为 1 就跳 $2^j$ ，跳之前 answer = min(answer, min_edge[x][j])。
同时上跳。 若此时 $x = y$ ，说明 $y$ 本来就是祖先，第 1 步的答案即最终答案。否则从高位到低位：只要 up[x][j] != up[y][j] 就让两点一起跳 $2^j$ ，两段的 min_edge 都并入答案。这一步结束时 $x,y$ 都停在 LCA 的儿子处。
最后一步。 各自再跳一条父边到达 LCA，这两条父边也是路径的一部分，它们的 min_edge[·][0] 必须并入答案。漏掉这一步是最常见的错误——倍增「跳到 LCA 儿子」的写法天然把最后一条边留在了外面。

注意 min_edge[x][j] 维护的是「向上 $2^j$ 条边」这段竖直路径的信息，而询问路径由「 $x$ 竖直段 + $y$ 竖直段」两段组成，两段各自取 min 后再合并即可。

代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203/**
 * 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-06-22 21:38
 * update_at: 2026-10-22 12:25
 */
// 货车运输：多次询问无向带权图中两点之间「路径最小边权」的最大值（最大瓶颈路）。
// 做法：Kruskal 按边权从大到小建最大生成森林，把原图瓶颈信息压缩成树上唯一路径，
// 再用倍增 LCA 在向上跳的同时维护路径最小边权，每个询问 O(log n)。
// 图不连通：森林天然分多个连通块，跨块询问输出 -1。
//
// 为什么树路径最小边权 = 原图最大瓶颈值（证明要点）：
// 设按权从大到小加边时 x、y 首次连通于权 W，则
//   只用权 >= W 的边已能连通 x、y，故答案 >= W；
//   只用权 > W 的边还不能连通 x、y，故任何 x->y 路径必含权 <= W 的边，答案 <= W。
// 而 Kruskal 结束时 x、y 在同一棵树里，树上路径都是已加入的边（权 >= W），
// 且两端到 LCA 的两段里必有一段含权恰为 W 的关键边，最小值恰为 W。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;    // 城市数上界 n <= 1e4
const int MAXM = 50005;    // 道路数上界 m <= 5e4
const int LOG = 15;        // 2^14 = 16384 > 1e4，够覆盖树深
const int INF = 1000000000;

// 一条无向道路：连接 u 和 v，限重 w。点编号 1..n。
struct Edge {
    int u;
    int v;
    int w;
};

int n, m, q;
Edge edge[MAXM];

// Kruskal 用的并查集
int father[MAXN];

// 最大生成森林（链式前向星存树边，双向）
int head[MAXN], to[MAXM * 2], weight_edge[MAXM * 2], nxt[MAXM * 2], edge_cnt;

int depth_node[MAXN];      // 树上深度，根为 1
int component[MAXN];       // 点所在的连通块编号，跨块询问输出 -1
int up[MAXN][LOG];         // up[x][j]：x 向上跳 2^j 条边到达的祖先，根之上为 0
int min_edge[MAXN][LOG];   // min_edge[x][j]：这段 2^j 条边的路径上最小限重

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;
}

void add_tree_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    weight_edge[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
}

void build_maximum_spanning_forest() {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    sort(edge + 1, edge + m + 1, cmp_edge);

    for (int i = 1; i <= m; i++) {
        if (merge_set(edge[i].u, edge[i].v)) {
            // 这条边连接了两个不同集合，进入最大生成森林
            add_tree_edge(edge[i].u, edge[i].v, edge[i].w);
            add_tree_edge(edge[i].v, edge[i].u, edge[i].w);
        }
    }
}

// 从 start 出发 BFS 遍历一个连通块，同时按层填倍增表
void bfs_component(int start, int cid) {
    queue<int> que;
    que.push(start);
    component[start] = cid;
    depth_node[start] = 1;
    up[start][0] = 0;
    min_edge[start][0] = INF;  // 根没有父边，填 INF 不影响取 min

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        // 出队时填表：此时 u 的 2^(j-1) 级祖先的表已填好
        for (int j = 1; j < LOG; j++) {
            up[u][j] = up[up[u][j - 1]][j - 1];
            min_edge[u][j] = min(min_edge[u][j - 1], min_edge[up[u][j - 1]][j - 1]);
        }

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == up[u][0]) {
                continue;  // 不走回父节点
            }
            component[v] = cid;
            depth_node[v] = depth_node[u] + 1;
            up[v][0] = u;
            min_edge[v][0] = weight_edge[i];
            que.push(v);
        }
    }
}

void prepare_lca() {
    int cid = 0;
    for (int i = 1; i <= n; i++) {
        if (component[i] == 0) {
            cid++;
            bfs_component(i, cid);  // 每个连通块单独 BFS，根深度为 1
        }
    }
}

// 询问 x 到 y 的最大载重：同块时是树上路径的最小边权，跨块为 -1
int query(int x, int y) {
    if (component[x] != component[y]) {
        return -1;  // 不在同一连通块，货车无法到达
    }

    int answer = INF;
    if (depth_node[x] < depth_node[y]) {
        swap(x, y);  // 让 x 是更深的那个
    }

    // 第一步：把 x 跳到与 y 同深度，沿途取最小边权
    int diff = depth_node[x] - depth_node[y];
    for (int j = LOG - 1; j >= 0; j--) {
        if ((diff & (1 << j)) != 0) {
            answer = min(answer, min_edge[x][j]);
            x = up[x][j];
        }
    }

    if (x == y) {
        return answer;  // y 本来就是 x 的祖先
    }

    // 第二步：两个点一起向上跳，跳到 LCA 的儿子为止
    for (int j = LOG - 1; j >= 0; j--) {
        if (up[x][j] != up[y][j]) {
            answer = min(answer, min_edge[x][j]);
            answer = min(answer, min_edge[y][j]);
            x = up[x][j];
            y = up[y][j];
        }
    }

    // 最后一步：各自跳到 LCA，这两条父边也是路径的一部分
    answer = min(answer, min_edge[x][0]);
    answer = min(answer, min_edge[y][0]);
    return answer;
}

void solve() {
    build_maximum_spanning_forest();
    prepare_lca();

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << query(x, y) << '\n';
    }
}

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

    read_input();
    solve();

    return 0;
}

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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126#!/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-22 12:26
# update_at: 2026-10-22 12:26
#
# main.py：货车运输。多次询问两点之间「路径最小边权」的最大值（最大瓶颈路）。
# 与 main.cpp 同一算法：Kruskal 建最大生成森林 + 倍增 LCA 维护路径最小边权。
# 图不连通时森林分多个连通块，跨块询问输出 -1。

import sys
from collections import deque

INF = 10**9  # 哨兵：根没有父边、以及题面不会出现的 x == y 询问；z <= 1e5 远小于它

# 树上每个节点存 (父亲, 到父亲的边权, 深度)；点编号 1..n
type Node = tuple[int, int, int]  # (parent, parent_edge_weight, depth)


def find(parent: list[int], x: int) -> int:
    """找 x 所在集合的根，顺路把路径上的点挂到根上（迭代压缩）。"""
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 只靠路径压缩：单次操作摊还 O(log n)，本题 n <= 1e4 已经足够
    parent = list(range(n + 1))
    edges: list[tuple[int, int, int]] = []
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        edges.append((u, v, w))

    # ---- Kruskal：按边权从大到小建最大生成森林，树边存成 children 列表 ----
    children: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for u, v, w in sorted(edges, key=lambda e: e[2], reverse=True):
        ru, rv = find(parent, u), find(parent, v)
        if ru != rv:
            parent[ru] = rv
            children[u].append((v, w))
            children[v].append((u, w))

    # ---- 每个连通块 BFS，求父亲、到父亲的边权、深度、连通块编号 ----
    nodes: list[Node] = [(-1, -1, -1)] * (n + 1)  # 根为 (0, INF, 1)
    component = [0] * (n + 1)  # component[x]：x 所在连通块编号
    cid = 0
    for start in range(1, n + 1):
        if component[start]:
            continue
        cid += 1
        nodes[start] = (0, INF, 1)
        component[start] = cid
        que = deque([start])
        while que:
            u = que.popleft()
            pu, _, du = nodes[u]
            for v, w in children[u]:
                if v == pu:  # 不走回父节点
                    continue
                nodes[v] = (u, w, du + 1)
                component[v] = cid
                que.append(v)

    # ---- 倍增表：up[j][x] 向上跳 2^j 条边的祖先，mn[j][x] 该段路径最小边权 ----
    LOG = max(1, (n).bit_length())  # 2^(LOG-1) >= n，覆盖最大树深
    up = [[-1] * (n + 1) for _ in range(LOG)]  # 用 -1 表示「根之上」的虚拟点
    mn = [[INF] * (n + 1) for _ in range(LOG)]
    for x in range(1, n + 1):
        up[0][x], mn[0][x] = nodes[x][0], nodes[x][1]

    for j in range(1, LOG):  # 递推：先跳 2^(j-1) 再跳 2^(j-1)
        upj, upj1 = up[j], up[j - 1]
        mnj, mnj1 = mn[j], mn[j - 1]
        for x in range(1, n + 1):
            mid = upj1[x]
            if mid < 0:
                upj[x], mnj[x] = -1, INF
            else:
                upj[x] = upj1[mid]
                mnj[x] = min(mnj1[x], mnj1[mid])

    # ---- 查询：深点先跳齐，再一起跳到 LCA，沿途取最小边权 ----
    def query(x: int, y: int) -> int:
        if component[x] != component[y]:
            return -1  # 不在同一连通块，货车无法到达
        answer = INF
        px, py = nodes[x], nodes[y]
        if px[2] < py[2]:  # 让 x 是更深的那个
            x, y = y, x
            px, py = py, px
        # 第一步：把 x 跳到与 y 同深度
        diff = px[2] - py[2]
        for j in range(LOG - 1, -1, -1):
            if diff >> j & 1:
                answer = min(answer, mn[j][x])
                x = up[j][x]
        if x == y:
            # y 本来就是 x 的祖先，刚才跳过的段就是全部路径
            return answer
        # 第二步：两个点一起向上跳到 LCA 的儿子
        for j in range(LOG - 1, -1, -1):
            if up[j][x] != up[j][y]:
                answer = min(answer, mn[j][x], mn[j][y])
                x, y = up[j][x], up[j][y]
        # 最后各自跳一条父边到 LCA
        answer = min(answer, mn[0][x], mn[0][y])
        return answer

    out = []
    q = next(data)
    for _ in range(q):
        x, y = next(data), next(data)
        out.append(str(query(x, y)))
    print("\n".join(out))


if __name__ == "__main__":
    main()

暴力对拍用 Floyd 改造版（把转移从加法换成「取 min 再取 max」）， $O(n^3)$ 只适合小数据：

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：Floyd 求任意两点最大瓶颈路，只适合小数据对拍。

const int MAXN = 55;

int n, m, q;
int best[MAXN][MAXN]; // best[i][j] 表示 i 到 j 能达到的最大路径瓶颈值。

void read_input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            best[i][j] = -1;
        }
        best[i][i] = 1000000000;
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        best[u][v] = max(best[u][v], w);
        best[v][u] = max(best[v][u], w);
    }
}

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (best[i][k] == -1 || best[k][j] == -1) {
                    continue;
                }
                int value = min(best[i][k], best[k][j]);
                if (value > best[i][j]) {
                    best[i][j] = value;
                }
            }
        }
    }
}

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

    read_input();
    floyd();

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << best[x][y] << '\n';
    }

    return 0;
}

复杂度

阶段	时间	空间
排序边表	$O(m \log m)$	$O(m)$
Kruskal 建最大生成森林	$O(m \,\alpha(n))$	$O(n + m)$
BFS + 倍增表预处理	$O(n \log n)$	$O(n \log n)$
单次询问	$O(\log n)$	—
总计	$O(m \log m + n \log n + q \log n)$	$O(m + n \log n)$

代入本题规模（ $n < 10^4$ 、 $m < 5\times10^4$ 、 $q < 3\times10^4$ ， $\log$ 约 14～17）：主项约 $10^6 \sim 5\times10^5$ 级别，远在时限内。

总结

「路径最小边权的最大值」是最大瓶颈路（maximin），与最短路（最小化边权和）目标不同，不能用 Dijkstra/Floyd 的加法框架。
核心性质：最大生成树路径上的最小边权 = 点对最大瓶颈值。证明用 Kruskal 阈值语言：按权从大到小放开边，两点首次连通时的阈值 $W$ 既是「存在全程 $\ge W$ 路径」的下界，又是「任何路径必含 $\le W$ 边」的上界。方向是最大生成树，选最小生成树会把阈值方向弄反。
图不连通时建最大生成森林，每个连通块的正确性独立成立；跨块询问不存在路径，输出 $-1$ 。
询问多的时候不要每次在原图上找路：先用最大生成森林把全部瓶颈信息压缩到树上，把点对查询变成树上路径查询，再用倍增 LCA 的 up[x][j] + min_edge[x][j] 双表 $O(\log n)$ 回答。上跳合并信息依赖 min 的结合律，最后一条父边别忘并入。
与 P1396 对读：一个是最小化路径最大边（minimin 阈值从小放开），一个是最大化路径最小边（maximax 阈值从大放开），骨架同为「阈值连通性 + Kruskal」，是同一族问题的两个方向。