最小生成树即最小瓶颈生成树,把每次询问化归为树上路径最大边权,用倍增 LCA 在 O(log n) 内回答。
OJ: roj
题目 ID: 1756
难度:提高
标签:最小生成树KruskalLCA倍增python
创建: 2026-10-07 21:55
更新: 2026-10-07 21:55
形式化题目
给定无向连通图
即路径上最贵的那一段决定总费用。每次询问给出
也就是所有
把边权看成"通行门槛",
数据范围:
正解
思路
朴素做法一:每个询问直接跑一次"最小瓶颈路"。 把边按权值排序后从小到大加边,
用并查集判断
朴素做法二:每个询问二分答案。 二分阈值
瓶颈在哪? 两种做法都在"每个询问重新处理整张图"。但这张图是固定的,
关键观察:最小生成树就是最小瓶颈生成树。 也就是
用 Kruskal 的过程证明最直观。按边权升序加边,设
- 答案
。 在只保留权 的边的子图里 与 不连通, 而 MST 上的 路径也是原图里的一条 路径,它的每条边都不在"权 "的子图里, 于是这条路径上必有一条权 的边,最大边权 。 - 答案
。 加入 之后, 与 在"只用权 的边"这个子图里已经连通, 所以 MST 中 的路径只用权 的边,最大边权 。
两式合并即得 MST 路径的最大边权恰为
于是问题被拆成两块:
- 建图: Kruskal 求出一棵 MST,
,这一步与 无关; - 询问: 在树上回答"两点路径的最大边权"。树上路径最值用倍增 LCA:
预处理
( 向上跳 步的祖先)与 (这 步路径上的最大边权), 每次询问先按深度差把较深的点抬上来,再让两点同步上跳直到停在 LCA 的下一层, 沿途对 取 即可, 。
边界与细节:
- 自环与重边:Kruskal 加边时两端点已经同属一个连通块就直接跳过,自环(
)天然被跳过; 重边里只有最小的那条有机会进 MST,其余被跳过,不影响答案。 的边:排序后最先被加进去,答案可以是 。 :空路径的最大值定义为 ,直接输出 (不要走"LCA 时取到某条边"的分支)。 - 数据保证连通,所以不需要处理"不连通"的情形;代码里把未访问点的祖先默认指向根, 只是防止越界。
- 深链爆栈:MST 可能是
的链,定向时用显式栈迭代 DFS,不用递归。
代码
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++ 版(同一算法):
/**
* 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 排序
;树上定向 ;倍增表 ; 每次询问 ,共 。 在 的顶格随机点上实测: main.cpp约 0.03 s (限时 1000 ms),main.py约 0.1 s(Python 3.14)——两者是同阶算法,Python 只是常数更大。 - 空间:C++ 侧
edge数组、倍增表 , 实测峰值 8.3 MB(限时 256 MB);Python 侧用列表存同样的表,峰值约 59 MB。 - 与朴素做法的关系:朴素做法一把"加边到连通"这一步按询问重复了
次, 正解把它换成一次性建 MST;朴素做法二把"连通性判定"按二分重复了 次, 正解把它换成倍增表上的 跳转。两条路都指向同一个结论:瓶颈在"重复处理整张图"。
总结
- 最小生成树 = 最小瓶颈生成树,这是本题的全部:
型的路径问题不需要对每个询问重跑图, 只要一次 MST,剩下的都是树上路径最值。结论的证明用 Kruskal 的加边时刻夹逼最干净。 - 把
次询问的公共部分提出来预处理,是"多询问 + 固定图"这类题的标准套路; 正解的预处理 与询问 是分开的两段,互不干扰。 - 倍增表存两样东西:祖先
up[k][v]和路径最值mx[k][v]。的合并式 与 up完全同构, 凡是"沿路径可合并的区间信息"都能这样挂上去(最大、最小、和、都一样)。 - 边界要单独想一遍:自环、重边、
、 、链状 MST 的深递归, 这五处任何一个漏掉都会在数据里翻车。 - 验证:题面样例与随仓
data/的 10 个测试点全部通过;另外把main.py、main.cpp分别与的最小瓶颈闭包暴力( f[i][j] = min_k max(f[i][k], f[k][j])) 在 400 / 200 组小随机图上对拍(含自环、重边、 、 ),结果完全一致。 - 本题素材源附带了数据生成脚本,
data/是自造的分层数据(边界点、小/中随机、顶格随机、 以及一条权值为的链加大量 补边的特殊结构),题面亦为网络重建, 与官方原始数据的分层方式可能不同;素材源的 std.cpp与本文算法一致(MST + 倍增 LCA), 这里按题面独立实现,并逐点跑过data/的全部 10 个测试点。
图示解析
以题面样例为例(
flowchart LR A["1"] -- "10" --- B["2"] A -- "20" --- C["3"] C -- "10" --- D["4"] A -. "100 已丢弃" .-> D B -. "30 已丢弃" .-> D
询问