过路费

GitHub跳转原题关系图返回列表

最小生成树即最小瓶颈生成树,把每次询问化归为树上路径最大边权,用倍增 LCA 在 O(log n) 内回答。

OJ: roj

题目 ID: 1756

难度:提高

标签:最小生成树KruskalLCA倍增python

创建: 2026-10-07 21:55

更新: 2026-10-07 21:55

形式化题目

给定无向连通图 G=(V,E)G = (V, E),∣V∣=n|V| = n,∣E∣=m|E| = m,每条边 ee 有非负权 w(e)w(e)(0⩽w⩽1090 \leqslant w \leqslant 10^9), 权值就是这条路的过路费。对一条路径 PP,定义它的费用为

cost(P)=max⁡e∈Pw(e),\mathrm{cost}(P) = \max_{e \in P} w(e),

即路径上最贵的那一段决定总费用。每次询问给出 S,TS, T,求

f(S,T)=min⁡P: S→Tmax⁡e∈Pw(e),f(S, T) = \min_{P:\, S \to T} \max_{e \in P} w(e),

也就是所有 S→TS \to T 路径中费用最小的那个值。题目保证图连通,所以答案总是存在; S=TS = T 时停在原地,费用为 00。

把边权看成"通行门槛",f(S,T)f(S,T) 的含义是:找到最小的阈值 XX,使得只保留权 ⩽X\leqslant X 的边时 SS 与 TT 仍然连通。这正是最小瓶颈路(minimax path)模型。

数据范围:1⩽n⩽1041 \leqslant n \leqslant 10^4,1⩽m⩽1051 \leqslant m \leqslant 10^5,1⩽q⩽1041 \leqslant q \leqslant 10^4, 0⩽w⩽1090 \leqslant w \leqslant 10^9(ww 可以为 00,也可以有重边与自环)。

正解

思路

朴素做法一:每个询问直接跑一次"最小瓶颈路"。 把边按权值排序后从小到大加边, 用并查集判断 SS、TT 何时连通,第一次连通时加入的边权就是答案。单次询问 O(mlog⁡m+mα)O(m \log m + m\alpha), qq 次就退化到 O(q mlog⁡m)O(q\,m \log m),在 q=m=105q = m = 10^5 量级上完全不可行。

朴素做法二:每个询问二分答案。 二分阈值 XX,只保留 w⩽Xw \leqslant X 的边做一次 BFS 判断 S,TS,T 是否连通。 单次 O((n+m)log⁡W)O((n + m)\log W),总量约 104×30×1.1×105≈3×101010^4 \times 30 \times 1.1 \times 10^5 \approx 3 \times 10^{10},同样过不去。

瓶颈在哪? 两种做法都在"每个询问重新处理整张图"。但这张图是固定的, qq 次询问问的是同一张图上的 qq 对点,所以应该先把图压缩成一份与询问无关的结构。

关键观察:最小生成树就是最小瓶颈生成树。 也就是

任意一棵 MST 上 u→v 路径的最大边权=f(u,v).\text{任意一棵 MST 上 } u \to v \text{ 路径的最大边权} = f(u, v).

用 Kruskal 的过程证明最直观。按边权升序加边,设 e∗e^{*} 是第一次让 uu 与 vv 连通的那条边, 它的权为 w∗w^{*}(这个值正是朴素做法一算出的答案)。分两步夹逼:

  • 答案 ⩾w∗\geqslant w^{*}。 在只保留权 <w∗< w^{*} 的边的子图里 uu 与 vv 不连通, 而 MST 上的 u→vu \to v 路径也是原图里的一条 u→vu \to v 路径,它的每条边都不在"权 <w∗< w^{*}"的子图里, 于是这条路径上必有一条权 ⩾w∗\geqslant w^{*} 的边,最大边权 ⩾w∗\geqslant w^{*}。
  • 答案 ⩽w∗\leqslant w^{*}。 加入 e∗e^{*} 之后,uu 与 vv 在"只用权 ⩽w∗\leqslant w^{*} 的边"这个子图里已经连通, 所以 MST 中 u→vu \to v 的路径只用权 ⩽w∗\leqslant w^{*} 的边,最大边权 ⩽w∗\leqslant w^{*}。

两式合并即得 MST 路径的最大边权恰为 w∗=f(u,v)w^{*} = f(u,v)。这也顺带解释了为什么 ff 与"选哪棵 MST" 无关:只要图连通,任意 MST 都给出同样的 w∗w^{*}。

于是问题被拆成两块:

  1. 建图: Kruskal 求出一棵 MST,O(mlog⁡m)O(m \log m),这一步与 qq 无关;
  2. 询问: 在树上回答"两点路径的最大边权"。树上路径最值用倍增 LCA: 预处理 upk[v]up_k[v](vv 向上跳 2k2^k 步的祖先)与 mxk[v]mx_k[v](这 2k2^k 步路径上的最大边权), 每次询问先按深度差把较深的点抬上来,再让两点同步上跳直到停在 LCA 的下一层, 沿途对 mxmx 取 max⁡\max 即可,O(log⁡n)O(\log n)。

边界与细节:

  • 自环与重边:Kruskal 加边时两端点已经同属一个连通块就直接跳过,自环(u=vu = v)天然被跳过; 重边里只有最小的那条有机会进 MST,其余被跳过,不影响答案。
  • w=0w = 0 的边:排序后最先被加进去,答案可以是 00。
  • S=TS = T:空路径的最大值定义为 00,直接输出 00(不要走"LCA 时取到某条边"的分支)。
  • 数据保证连通,所以不需要处理"不连通"的情形;代码里把未访问点的祖先默认指向根, 只是防止越界。
  • 深链爆栈:MST 可能是 n=104n = 10^4 的链,定向时用显式栈迭代 DFS,不用递归。

代码

Python 版:

python
#!/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-07 21:55
# update_at: 2026-10-07 21:55

import sys

ROOT = 1  # MST 的根取城市 1;图保证连通,根取谁都不影响路径上的最大边权

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Edge = tuple[int, int, int]        # (u, v, w) 一条双向道路及其过路费
type Adj = list[list[tuple[int, int]]]  # adj[u] = [(相邻城市, 这条路的费用), ...]
type Jump = list[list[int]]             # jump[k][v] = v 向上跳 2^k 步的祖先 / 这段最大边权


def find_root(parent: list[int], x: int) -> int:
    """并查集查根(带路径压缩),Kruskal 用它判断两个城市是否已经连通。"""
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root


def build_mst(n: int, edges: list[Edge]) -> Adj:
    """Kruskal 求最小生成树,返回它的邻接表。

    最小生成树就是最小瓶颈生成树:MST 上 u-v 路径的最大边权等于全图所有 u-v 路径
    最大边权的最小值,所以"最少过路费"完全由 MST 决定,与其它边无关。
    """
    parent = list(range(n + 1))
    adj: Adj = [[] for _ in range(n + 1)]
    for u, v, w in sorted(edges, key=lambda e: e[2]):  # 按费用从小到大加边
        ru, rv = find_root(parent, u), find_root(parent, v)
        if ru == rv:
            continue  # 已成环(含自环),这条边不属于 MST
        parent[ru] = rv
        adj[u].append((v, w))
        adj[v].append((u, w))
    return adj


def orient_tree(adj: Adj, n: int) -> tuple[list[int], list[int], list[int]]:
    """把 MST 以 ROOT 为根定向,返回 (深度, 父亲, 到父亲的边权)。

    用显式栈迭代,链状数据不会爆递归栈。
    """
    depth = [0] * (n + 1)
    up0 = [ROOT] * (n + 1)  # 默认祖先为根:题面保证连通,这里只是防越界
    mx0 = [0] * (n + 1)
    seen = [False] * (n + 1)
    seen[ROOT] = True
    stack = [ROOT]
    while stack:
        u = stack.pop()
        for v, w in adj[u]:
            if seen[v]:
                continue
            seen[v] = True
            depth[v] = depth[u] + 1
            up0[v], mx0[v] = u, w
            stack.append(v)
    return depth, up0, mx0


def build_jump(up0: list[int], mx0: list[int]) -> tuple[Jump, Jump]:
    """倍增表:up[k][v] = v 向上 2^k 步的祖先,mx[k][v] = 这 2^k 步里的最大边权。"""
    up, mx = [up0], [mx0]
    for _ in range(1, len(up0).bit_length()):
        prev_up, prev_mx = up[-1], mx[-1]
        up.append([prev_up[x] for x in prev_up])                   # 祖先表翻倍
        mx.append([max(m, prev_mx[x]) for m, x in zip(prev_mx, prev_up)])  # 两段取最大
    return up, mx


def path_max(up: Jump, mx: Jump, depth: list[int], s: int, t: int) -> int:
    """S -> T 在 MST 上的路径最大边权,就是最少过路费;S == T 时为 0。"""
    if s == t:
        return 0  # 原地不动,不用交过路费
    a, b = (s, t) if depth[s] >= depth[t] else (t, s)
    ans = 0
    diff = depth[a] - depth[b]
    for k in range(diff.bit_length()):  # 先把 a 抬到与 b 同深度
        if diff >> k & 1:
            ans = max(ans, mx[k][a])
            a = up[k][a]
    if a == b:
        return ans  # b 就是 a 的祖先,LCA 已找到
    for k in range(len(up) - 1, -1, -1):  # 一起往上跳,停在 LCA 的下一层
        if up[k][a] != up[k][b]:
            ans = max(ans, mx[k][a], mx[k][b])
            a, b = up[k][a], up[k][b]
    return max(ans, mx[0][a], mx[0][b])  # 再各走一步到 LCA


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    edges: list[Edge] = [(next(data), next(data), next(data)) for _ in range(m)]

    depth, up0, mx0 = orient_tree(build_mst(n, edges), n)
    up, mx = build_jump(up0, mx0)

    q = next(data)
    ans = [str(path_max(up, mx, depth, next(data), next(data))) for _ in range(q)]
    print('\n'.join(ans))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * 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-07 21:55
 * update_at: 2026-10-07 21:55
 */
// 一本通 1756《过路费》
// 题意:无向连通图,n 个城市 m 条双向道路,边权 w 就是这段路要交的过路费。
//       一次 S->T 的总费用 = 路径上边权的最大值。每次询问求这个最大值的最小可能值。
// 算法:最小生成树就是最小瓶颈生成树 —— MST 上 u-v 路径的最大边权,等于全图所有
//       u-v 路径最大边权的最小值。于是询问全部化归为"树上路径最大边权",
//       用倍增 LCA 在 O(log n) 内回答。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10005;   // 城市数上限 1e4
const int MAXM = 100005;  // 道路数上限 1e5
const int LOGN = 15;      // 2^14 = 16384 > n - 1,向上跳 2^k 步的层数够用
const int ROOT = 1;       // MST 以城市 1 为根;图保证连通,根取谁都不影响路径最大边权

struct Edge {  // 读入的一条道路
    int u;
    int v;
    ll w;      // 边权(过路费),最大 1e9
};
Edge edge[MAXM];

struct Link {  // MST 的链式前向星(MST 只有 n-1 条边,双向存 2n 个结点)
    int to;
    ll w;
    int nxt;
};
Link link[2 * MAXN];
int head[MAXN];   // head[u] 为城市 u 的第一条出边编号,0 表示没有
int link_cnt;

struct Jump {  // 倍增表的一项
    int anc;   // 向上跳 2^k 步到达的祖先
    ll mxw;    // 这 2^k 步路径上的最大边权
};
Jump jp[LOGN][MAXN];  // jp[k][v]:从城市 v 向上跳 2^k 步的信息

int dsu[MAXN];    // 并查集,Kruskal 用来判断两个城市是否已连通
char vis[MAXN];   // vis[v]:给 MST 定向时 v 是否已入树(只有 0/1,用 char 省内存)
int depth[MAXN];  // depth[v]:MST 上 v 到根的步数,根为 0
int n, m, q;

void add_link(int u, int v, ll w) {
    link_cnt++;
    link[link_cnt].to = v;
    link[link_cnt].w = w;
    link[link_cnt].nxt = head[u];
    head[u] = link_cnt;
}

// 并查集查根,带路径压缩
int find_root(int x) {
    while (dsu[x] != x) {
        dsu[x] = dsu[dsu[x]];
        x = dsu[x];
    }
    return x;
}

bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

// Kruskal 求最小生成树,结果建成链式前向星
void build_mst() {
    sort(edge + 1, edge + m + 1, cmp_edge);
    for (int i = 1; i <= n; i++) dsu[i] = i;
    for (int i = 1; i <= m; i++) {
        int ru = find_root(edge[i].u);
        int rv = find_root(edge[i].v);
        if (ru == rv) continue;  // 已成环(含自环),这条边不会出现在任何最小瓶颈路径上
        dsu[ru] = rv;
        add_link(edge[i].u, edge[i].v, edge[i].w);
        add_link(edge[i].v, edge[i].u, edge[i].w);
    }
}

// 以 ROOT 为根给 MST 定向,再逐层拼出倍增表
void build_jump() {
    for (int v = 1; v <= n; v++) {  // 未访问点也指向 ROOT,防止越界(题面保证连通)
        jp[0][v].anc = ROOT;
        jp[0][v].mxw = 0;
    }
    int stk[MAXN];  // 显式栈做迭代 DFS,链状数据不会爆递归栈
    int top = 0;
    stk[top++] = ROOT;
    vis[ROOT] = 1;
    while (top > 0) {
        int u = stk[--top];
        for (int e = head[u]; e != 0; e = link[e].nxt) {
            int v = link[e].to;
            if (vis[v]) continue;
            vis[v] = 1;
            depth[v] = depth[u] + 1;
            jp[0][v].anc = u;
            jp[0][v].mxw = link[e].w;
            stk[top++] = v;
        }
    }
    for (int k = 1; k < LOGN; k++) {
        for (int v = 1; v <= n; v++) {
            int mid = jp[k - 1][v].anc;  // 先跳 2^(k-1) 步落到的中点
            jp[k][v].anc = jp[k - 1][mid].anc;
            jp[k][v].mxw = max(jp[k - 1][v].mxw, jp[k - 1][mid].mxw);
        }
    }
}

// 求 S->T 在 MST 上的路径最大边权,即最少过路费
ll query_max(int s, int t) {
    if (s == t) return 0;  // 原地不动,不用交过路费
    ll ans = 0;
    int a = s, b = t;
    if (depth[a] < depth[b]) swap(a, b);
    int diff = depth[a] - depth[b];
    for (int k = 0; k < LOGN; k++) {  // 先把 a 抬到与 b 同深度
        if (diff >> k & 1) {
            ans = max(ans, jp[k][a].mxw);
            a = jp[k][a].anc;
        }
    }
    if (a == b) return ans;           // b 就是 a 的祖先,LCA 已找到
    for (int k = LOGN - 1; k >= 0; k--) {  // 一起往上跳,停在 LCA 的下一层
        if (jp[k][a].anc != jp[k][b].anc) {
            ans = max(ans, jp[k][a].mxw);
            ans = max(ans, jp[k][b].mxw);
            a = jp[k][a].anc;
            b = jp[k][b].anc;
        }
    }
    ans = max(ans, jp[0][a].mxw);  // 再各走一步到 LCA
    ans = max(ans, jp[0][b].mxw);
    return ans;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        scanf("%d %d %lld", &u, &v, &w);
        edge[i].u = u;
        edge[i].v = v;
        edge[i].w = w;
    }
    build_mst();
    build_jump();
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int s, t;
        scanf("%d %d", &s, &t);
        printf("%lld\n", query_max(s, t));
    }
    return 0;
}

复杂度

  • 时间:Kruskal 排序 O(mlog⁡m)O(m \log m);树上定向 O(n)O(n);倍增表 O(nlog⁡n)O(n \log n); 每次询问 O(log⁡n)O(\log n),共 O(mlog⁡m+(n+q)log⁡n)O(m \log m + (n + q)\log n)。 在 n=104,m=105,q=104n = 10^4, m = 10^5, q = 10^4 的顶格随机点上实测:main.cpp 约 0.03 s (限时 1000 ms),main.py 约 0.1 s(Python 3.14)——两者是同阶算法,Python 只是常数更大。
  • 空间:C++ 侧 edge 数组 105×16B10^5 \times 16\text{B}、倍增表 15×104×16B15 \times 10^4 \times 16\text{B}, 实测峰值 8.3 MB(限时 256 MB);Python 侧用列表存同样的表,峰值约 59 MB。
  • 与朴素做法的关系:朴素做法一把"加边到连通"这一步按询问重复了 qq 次, 正解把它换成一次性建 MST;朴素做法二把"连通性判定"按二分重复了 log⁡W\log W 次, 正解把它换成倍增表上的 O(log⁡n)O(\log n) 跳转。两条路都指向同一个结论:瓶颈在"重复处理整张图"。

总结

  • 最小生成树 = 最小瓶颈生成树,这是本题的全部:min⁡max⁡\min \max 型的路径问题不需要对每个询问重跑图, 只要一次 MST,剩下的都是树上路径最值。结论的证明用 Kruskal 的加边时刻夹逼最干净。
  • 把 qq 次询问的公共部分提出来预处理,是"多询问 + 固定图"这类题的标准套路; 正解的预处理 O(mlog⁡m)O(m\log m) 与询问 O(qlog⁡n)O(q\log n) 是分开的两段,互不干扰。
  • 倍增表存两样东西:祖先 up[k][v] 和路径最值 mx[k][v]。mxmx 的合并式 mxk[v]=max⁡(mxk−1[v],mxk−1[ upk−1[v] ])mx_k[v] = \max(mx_{k-1}[v], mx_{k-1}[\,up_{k-1}[v]\,]) 与 up 完全同构, 凡是"沿路径可合并的区间信息"都能这样挂上去(最大、最小、和、gcd⁡\gcd 都一样)。
  • 边界要单独想一遍:自环、重边、w=0w = 0、S=TS = T、链状 MST 的深递归, 这五处任何一个漏掉都会在数据里翻车。
  • 验证:题面样例与随仓 data/ 的 10 个测试点全部通过;另外把 main.py、main.cpp 分别与 O(n3)O(n^3) 的最小瓶颈闭包暴力(f[i][j] = min_k max(f[i][k], f[k][j])) 在 400 / 200 组小随机图上对拍(含 n=1n = 1 自环、重边、w=0w = 0、S=TS = T),结果完全一致。
  • 本题素材源附带了数据生成脚本,data/ 是自造的分层数据(边界点、小/中随机、顶格随机、 以及一条权值为 ii 的链加大量 10910^9 补边的特殊结构),题面亦为网络重建, 与官方原始数据的分层方式可能不同;素材源的 std.cpp 与本文算法一致(MST + 倍增 LCA), 这里按题面独立实现,并逐点跑过 data/ 的全部 10 个测试点。

图示解析

以题面样例为例(n=4n = 4,边 1 ⁣− ⁣2:101\!-\!2:10、1 ⁣− ⁣3:201\!-\!3:20、1 ⁣− ⁣4:1001\!-\!4:100、2 ⁣− ⁣4:302\!-\!4:30、3 ⁣− ⁣4:103\!-\!4:10): 按权值升序加边,1 ⁣− ⁣21\!-\!2(1010)与 3 ⁣− ⁣43\!-\!4(1010)先进,1 ⁣− ⁣31\!-\!3(2020)把两块拼起来, 此时 4 个城市已连通,剩下的 1 ⁣− ⁣41\!-\!4(100100)、2 ⁣− ⁣42\!-\!4(3030)全部跳过。

flowchart LR
  A["1"] -- "10" --- B["2"]
  A -- "20" --- C["3"]
  C -- "10" --- D["4"]
  A -. "100 已丢弃" .-> D
  B -. "30 已丢弃" .-> D

询问 1→41 \to 4:MST 上路径是 1→3→41 \to 3 \to 4,最大边权 max⁡(20,10)=20\max(20, 10) = 20; 原图里更直接的 1→41 \to 4 要走 100100 的边,反而更贵,这正是"最大边权最小"与"边权和最小"的差别。 询问 4→14 \to 1 走同一条路径,答案同为 2020——ff 是对称的,路径反向不改变最大值。