[NOIP2013-提高]货车运输

形式化题目

给定 $n$ 个点、 $m$ 条带权无向边的图，边权为该边的「限重」。 $q$ 个询问：求点 $x$ 到点 $y$ 的所有路径中，路径上最小边权的最大值（瓶颈路）；若两点不连通输出 $-1$ 。数据范围： $n < 10^4$ ， $m < 5 \times 10^4$ ， $q < 3 \times 10^4$ ， $0 \leqslant z \leqslant 10^5$ ，两座城市之间可能有多条道路。

正解

思路

1. 朴素做法为什么不行

最直接的想法是：对每个询问，在图上枚举 / 搜索从 $x$ 到 $y$ 的所有路径，分别记录路径最小边权，取最大值。路径数量是指数级的，即使加剪枝， $q$ 高达 $3 \times 10^4$ 个询问也完全不可行。瓶颈在于：每次询问都在"重新看一遍整张图"，而询问之间其实共享大量结构。

2. 关键观察：答案一定在最大生成树上

把答案换个说法： $x$ 到 $y$ 能运的货物最重是 $W$ ，等价于 只保留限重 $\geqslant W$ 的边 时 $x$ 与 $y$ 连通。

现在考察最大生成树的 Kruskal 构造过程：把所有边按限重从大到小排序，依次加入能用（不形成环）的边。设阈值 $W$ ，考虑"只保留限重 $\geqslant W$ 的边"的图 $G_W$ ，以及"最大生成树删去限重 $< W$ 的树边"得到的森林 $T_W$ ：

Kruskal 扫到限重 $\geqslant W$ 的边时，它与在 $G_W$ 中做"不断合并连通块"的过程完全一致——两者最终形成的连通块集合相同。

于是 $x, y$ 在 $G_W$ 中连通 $\iff$ $x, y$ 在 $T_W$ 中连通。令 $W^\*$ 为树上 $x$ 到 $y$ 路径的最小边权，那么：

$W \leqslant W^\*$ 时，路径上每条边限重都 $\geqslant W$ ，两点在 $T_W$ 中沿这条路径连通，原图也连通；
$W > W^\*$ 时，树路径被切断， $T_W$ 中两点不连通，原图同样不连通。

所以 $x, y$ 的答案恰好等于最大生成树上 $x$ 到 $y$ 路径的最小边权。一句话：货车总可以放弃一些限重小的边不走，最优方案只需要 $n-1$ 条树边。

3. 树上查询：倍增

树定根后（BFS 确定父亲和深度），询问"路径最小边权"可以用倍增解决。定义：

$up[k][v]$ ： $v$ 往上走 $2^k$ 步到达的祖先；
$mn[k][v]$ ： $v$ 往上走 $2^k$ 步这段路上最小的边权。

递推式：

up[k][v] = up[k-1][\,up[k-1][v]\,]

mn[k][v] = \min\big(mn[k-1][v],\ mn[k-1][\,up[k-1][v]\,]\big)

查询 $(x, y)$ 时，与求 LCA 完全同套路，只是每次"跳"的时候顺带对 $mn$ 取 min：

若两点不连通（最终并查集代表元不同），直接输出 $-1$ ；
把较深的一方按二进制拆分提升到与另一方同深度，沿途累计最小边权；
若此时两点重合，答案已经算出；
否则两点一起从高往低试： $2^k$ 级祖先不同就一起跳上去，最后停在 LCA 的下一层，再把最后一步的边权计入。

图示解析

以样例为例：4 座城市，道路 $1\!-\!2(4)$ 、 $2\!-\!3(3)$ 、 $3\!-\!1(1)$ 。Kruskal 按限重从大到小加边：

顺序	边	限重	动作
1	$1-2$	4	加入
2	$2-3$	3	加入
3	$3-1$	1	会成环，舍弃

最大生成树（以 1 为根）：

flowchart TB
    A["1"] -->|"限重 4"| B["2"]
    B -->|"限重 3"| C["3"]

查询 $1 \to 3$ ：路径是 $1 \xrightarrow{4} 2 \xrightarrow{3} 3$ ，瓶颈 = $\min(4,3) = 3$ ，与样例输出一致。被舍弃的 $3\!-\!1(1)$ 永远不会被最优路线用到——它正是"能被更宽的绕路取代"的那类边。

查询 $1 \to 4$ ：城市 4 不在任何树中，并查集判出不连通，输出 $-1$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
struct Edge{int x,y,z;}; struct Adj{int v,w;};
int find_set(vector<int>&fa,int x){while(fa[x]!=x){fa[x]=fa[fa[x]]; x=fa[x];} return x;}
bool cmp_edge(const Edge&a,const Edge&b){return a.z>b.z;}
int main(){ios::sync_with_stdio(false); cin.tie(nullptr); int n,m; if(!(cin>>n>>m)) return 0; vector<Edge> edges(m); for(int i=0;i<m;i++) cin>>edges[i].x>>edges[i].y>>edges[i].z; vector<int> fa(n+1); for(int i=1;i<=n;i++) fa[i]=i; vector<vector<Adj> > tree(n+1); sort(edges.begin(),edges.end(),cmp_edge); for(int i=0;i<m;i++){int rx=find_set(fa,edges[i].x), ry=find_set(fa,edges[i].y); if(rx!=ry){fa[rx]=ry; tree[edges[i].x].push_back({edges[i].y,edges[i].z}); tree[edges[i].y].push_back({edges[i].x,edges[i].z});}}
    vector<int> parent(n+1), upw(n+1), depth(n+1), seen(n+1); for(int root=1;root<=n;root++) if(!seen[root]){queue<int> q; q.push(root); seen[root]=1; while(!q.empty()){int u=q.front();q.pop(); for(int i=0;i<(int)tree[u].size();i++){int v=tree[u][i].v,w=tree[u][i].w; if(!seen[v]){seen[v]=1;parent[v]=u;upw[v]=w;depth[v]=depth[u]+1;q.push(v);}}}}
    int LOG=14; vector<vector<int> > up(LOG, vector<int>(n+1)), mn(LOG, vector<int>(n+1)); up[0]=parent; mn[0]=upw; for(int k=1;k<LOG;k++) for(int v=0;v<=n;v++){up[k][v]=up[k-1][up[k-1][v]]; mn[k][v]=min(mn[k-1][v], mn[k-1][up[k-1][v]]);} int qn; cin>>qn; while(qn--){int x,y;cin>>x>>y; if(find_set(fa,x)!=find_set(fa,y)){cout<<-1<<'\n'; continue;} if(depth[x]<depth[y]) swap(x,y); int ans=INF, diff=depth[x]-depth[y]; for(int k=0;k<LOG;k++) if((diff>>k)&1){ans=min(ans,mn[k][x]); x=up[k][x];} if(x==y){cout<<ans<<'\n'; continue;} for(int k=LOG-1;k>=0;k--) if(up[k][x]!=up[k][y]){ans=min(ans,min(mn[k][x],mn[k][y])); x=up[k][x]; y=up[k][y];} cout<<min(ans,min(mn[0][x],mn[0][y]))<<'\n';} 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#!/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-02 10:29
# update_at: 2026-10-02 10:29

import sys
from collections import deque

LOG = 14   # 2^14 > 10^4，倍增层数足够覆盖任意树深
INF = 1 << 30


def find(fa: list[int], x: int) -> int:
    """并查集找代表元，隔代路径压缩。"""
    while fa[x] != x:
        fa[x] = fa[fa[x]]
        x = fa[x]
    return x


def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[list[list[tuple[int, int]]], list[int]]:
    """按限重从大到小做最大生成树：返回带权邻接表与最终并查集。

    货车想运得越重越好，所以走"瓶颈最大"的路径——它一定在最大生成树上。
    """
    fa = list(range(n + 1))
    tree: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for x, y, z in sorted(edges, key=lambda e: e[2], reverse=True):  # 按限重 z 从大到小
        rx, ry = find(fa, x), find(fa, y)
        if rx != ry:
            fa[rx] = ry
            tree[x].append((y, z))
            tree[y].append((x, z))
    return tree, fa


def bfs_root(root: int, tree: list[list[tuple[int, int]]], parent: list[int],
             up_w: list[int], depth: list[int], seen: list[bool]) -> None:
    """从 root 出发 BFS，确定每个点的父亲、到父亲的边权和深度。"""
    seen[root] = True
    dq = deque([root])
    while dq:
        u = dq.popleft()
        for v, w in tree[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                up_w[v] = w
                depth[v] = depth[u] + 1
                dq.append(v)


def build_tables(n: int, tree: list[list[tuple[int, int]]]) -> tuple[list[list[int]], list[list[int]], list[int]]:
    """建倍增表：up[k][v] 是 v 往上 2^k 级祖先，mn[k][v] 是这段路上最小的限重。"""
    parent = [0] * (n + 1)
    up_w = [0] * (n + 1)   # 每个点到父亲的边权
    depth = [0] * (n + 1)
    seen = [False] * (n + 1)
    for root in range(1, n + 1):          # 生成树可能是森林，每个连通块都要 BFS
        if not seen[root]:
            bfs_root(root, tree, parent, up_w, depth, seen)

    up = [parent[:]]                      # 第 0 层就是父亲数组
    mn = [up_w[:]]
    for _ in range(1, LOG):
        prev_up, prev_mn = up[-1], mn[-1]
        up.append([prev_up[prev_up[v]] for v in range(n + 1)])
        mn.append([min(prev_mn[v], prev_mn[prev_up[v]]) for v in range(n + 1)])
    return up, mn, depth


def query(x: int, y: int, up: list[list[int]], mn: list[list[int]],
          depth: list[int], fa: list[int]) -> int:
    """x 到 y 在最大生成树上的路径最小限重；不在同一连通块返回 -1。"""
    if find(fa, x) != find(fa, y):
        return -1
    if depth[x] < depth[y]:
        x, y = y, x
    ans = INF
    # 先把较深的一方按二进制拆分提升到与另一方同深度，沿途取最小边权
    diff = depth[x] - depth[y]
    for k in range(LOG):
        if diff >> k & 1:
            ans = min(ans, mn[k][x])
            x = up[k][x]
    if x == y:
        return ans
    # 两人一起从高处往下试：2^k 级祖先不同就跳上去，最后在 LCA 的下一层停下
    for k in range(LOG - 1, -1, -1):
        if up[k][x] != up[k][y]:
            ans = min(ans, mn[k][x], mn[k][y])
            x, y = up[k][x], up[k][y]
    return min(ans, mn[0][x], mn[0][y])


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

    edges = [(next(data), next(data), next(data)) for _ in range(m)]  # (x, y, z)
    q = next(data)
    queries = [(next(data), next(data)) for _ in range(q)]

    tree, fa = kruskal(n, edges)
    up, mn, depth = build_tables(n, tree)

    print('\n'.join(str(query(x, y, up, mn, depth, fa)) for x, y in queries))


if __name__ == "__main__":
    solve()

实现上的两个要点：

图可能不连通：生成树实际是森林。build_tables 里对每个还没访问过的点都做一次 BFS；query 开头用 Kruskal 遗留下来的最终并查集判断连通性。
哨兵与 $z=0$ ：限重可以为 0，所以查询的初值必须设成 $+\infty$ （INF）而不是 0，否则有 0 限重边的数据会算错。

复杂度

时间：Kruskal 排序 $O(m \log m)$ ；BFS 建树 $O(n + m)$ ；倍增表 $O(n \log n)$ ；每个询问 $O(\log n)$ ，共 $q$ 个 → 总计 $O\big(m \log m + (n + q)\log n\big)$ ，对 $n < 10^4$ 、 $m < 5 \times 10^4$ 、 $q < 3 \times 10^4$ 绰绰有余。
空间：倍增表 $O(n \log n)$ ，约 $10^4 \times 14$ 个整数，远小于 32MB 限制。
注：Python 版在最大数据上实测约 0.9s/测例，OJ 限时 1s 属于贴线（算法本身复杂度与 C++ 正解同阶）。

总结

这道题的钥匙是一个等价转换：「最大载重」=「瓶颈路径」=「只保留限重 $\geqslant W$ 的边时是否连通」，而这个连通性恰由最大生成树刻画，于是 $q$ 个图上询问全部塌缩成树上的路径最小值。
树上路径极值 + 多组询问的标准武器是倍增 LCA：一张 $2^k$ 跳表，跳的时候多带一维 min 就能回答路径 min。
容易漏的边界：图不连通（森林）、答案为 0（哨兵初值不能取 0）、重边（Kruskal 天然处理）。