1 问题
给定无向带权图,反复询问两个不同顶点
记一条路径
目标为
它最小化的是一条路径上的最大值,不是边权和。若边权表示危险程度,就是寻找“最危险的一段也尽量安全”的路线。
本篇先用 最小生成树 压缩原图,再用 爬树法求 LCA(倍增) 的倍增方法维护树上路径信息。
2 示例
沿用基础篇的五点八边图。比较从
| 路线 | 边权 | 路径和 | 最大边 |
|---|---|---|---|
第三条路虽然总长度更大,瓶颈却更小。它正是前文所选 MST 中连接
3 MST 上的路径
在无向连通带权图中,任取一棵 MST。任意两个不同顶点之间,MST 上唯一路径的最大边权,等于原图中的最小瓶颈值。
结论允许同权边,也不要求 MST 唯一。不同 MST 上的具体路径可能不同,但同一对点查询出的最大边权相同。
3.1 删边证明
设
任意原图中的
若存在这样的边满足
与
MST 自己的路径恰好达到
3.2 阈值理解
只保留权值不超过
所以
这与 Kruskal 从小到大加入边的过程一致。单次询问可以按权扫描到两点连通;大量询问则保存生成树,再做树上查询。不要为每次询问重新排序和扫描全部边。
4 倍增查询
4.1 保存树边
Kruskal 选边成功时,将原图中的这条边加入树的邻接表。原图不连通时,会得到多棵树,即最小生成森林;每个连通分量内部仍可使用瓶颈路性质。
并查集只负责判断两点是否连通,树的邻接表负责保存路径,不能用并查集父亲指针代替。
4.2 路径最大值
在祖先表之外,维护
若
根没有父边,空段的最大值使用负无穷作为单位元;这样零权和负权边也不会被初值
在样例 MST 的链
| 从 |
到达点 | 经过边权 | 最大值 |
|---|---|---|---|
4.3 查询过程
与倍增求 LCA 相同,区别是每次移动时把所经过的路径最大值并入答案:
- 较深点先升到同一深度。
- 若两点已重合,返回累计结果。
- 从大到小同时上跳,保持两点的祖先不同。
- 最后补上两条通向 LCA 的父边。
查询
5 代码
采用 luogu P2245: 星际导航 的边表与询问格式:
- 输入
,再输入 条 u v w。 - 输入询问数
,再输入 对顶点。 - 连通时输出最小瓶颈值,不连通输出
impossible。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const int maxm = 300000 + 5;
struct Edge {
int u, v, id;
ll w;
};
Edge e[maxm];
int fa[maxn], sz[maxn];
void init(int n) {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
sz[i] = 1;
}
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (sz[fx] < sz[fy]) swap(fx, fy);
fa[fy] = fx;
sz[fx] += sz[fy];
return true;
}
bool cmp(const Edge &a, const Edge &b) {
if (a.w != b.w) return a.w < b.w;
return a.id < b.id; // 同权时按输入顺序,便于与正文示例核对
}
const int LOG = 18; // 2^18 > 100000,下标 0..17
const ll NEG = -(1LL << 62);
struct TreeEdge {
int to;
ll w;
};
vector<TreeEdge> g[maxn]; // 保存选中的原图边,不是并查集父亲指针
int dep[maxn], up[maxn][LOG], que[maxn];
ll mx[maxn][LOG]; // 向上 2^j 步的路径最大边权
void build_forest(int n, int m) {
init(n);
for (int u = 1; u <= n; ++u) g[u].clear();
sort(e, e + m, cmp);
for (int i = 0; i < m; ++i) {
if (!unite(e[i].u, e[i].v)) continue;
g[e[i].u].push_back({e[i].v, e[i].w});
g[e[i].v].push_back({e[i].u, e[i].w});
}
for (int u = 0; u <= n; ++u) {
dep[u] = 0;
for (int j = 0; j < LOG; ++j) {
up[u][j] = 0;
mx[u][j] = NEG; // 空路径不能初始化为 0,否则负边权会出错
}
}
// 原图可能不连通:对森林中的每棵树分别预处理。
for (int root = 1; root <= n; ++root) {
if (dep[root]) continue;
int head = 0, tail = 0;
que[tail++] = root;
dep[root] = 1;
while (head < tail) {
int u = que[head++];
for (auto [v, w] : g[u]) {
if (v == up[u][0]) continue;
dep[v] = dep[u] + 1;
up[v][0] = u;
mx[v][0] = w;
for (int j = 1; j < LOG; ++j) {
int p = up[v][j - 1];
up[v][j] = up[p][j - 1];
mx[v][j] = max(mx[v][j - 1], mx[p][j - 1]);
}
que[tail++] = v;
}
}
}
}
// 调用前确认两点连通。相同点按本模板的接口约定返回 0。
ll path_max(int u, int v) {
if (u == v) return 0;
ll answer = NEG;
if (dep[u] < dep[v]) swap(u, v);
int diff = dep[u] - dep[v];
for (int j = LOG - 1; j >= 0; --j) {
if (diff >> j & 1) {
answer = max(answer, mx[u][j]);
u = up[u][j];
}
}
if (u == v) return answer;
for (int j = LOG - 1; j >= 0; --j) {
if (up[u][j] != up[v][j]) {
answer = max(answer, max(mx[u][j], mx[v][j]));
u = up[u][j];
v = up[v][j];
}
}
return max(answer, max(mx[u][0], mx[v][0]));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> e[i].u >> e[i].v >> e[i].w;
e[i].id = i;
}
build_forest(n, m);
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
if (find(u) != find(v)) cout << "impossible\n";
else cout << path_max(u, v) << '\n';
}
return 0;
}
代码对每棵树分别进行队列遍历,建立祖先表。即使生成树退化成链,也不需要递归遍历。
输入:
5 8
1 2 1
2 3 2
1 3 2
3 4 4
2 4 5
4 5 3
3 5 6
1 5 8
5
1 5
1 3
4 5
2 5
3 3
输出:
4
2
3
4
0
数学性质只讨论不同顶点。对 u==v,本模板额外约定返回
6 最大承重
luogu P1967: [NOIP 2013 提高组] 货车运输 的目标相反:一条路径能承受的重量,等于其中最小的限重,希望这个最小值尽量大:
使用最大生成树上的路径最小值即可求解。证明仍用删边换边:若树路径最小边为
修改时要同时调整三个地方:
| 最小瓶颈路 | 最大承重 |
|---|---|
| 按边权升序建最小生成森林 | 按边权降序建最大生成森林 |
| 倍增维护路径最大值 | 倍增维护路径最小值 |
| 空段使用负无穷 | 空段使用正无穷 |
只改排序方向不够,查询的合并运算与初值也要一起改。原题还要求不连通时输出
7 瓶颈生成树
“整棵树最大边最小”叫最小瓶颈生成树,它与“两点瓶颈路”相关,但不是同一个定义。
MST 一定是最小瓶颈生成树:任取一棵其他生成树,删去 MST 的一条全局最大边后,其他生成树也必须跨过这个切分,因此其最大边不会更小。
反过来不成立。三角形边权为
这种树也不保证保留所有点对的最优瓶颈:原图中权值为
8 复杂度与边界
设询问数为
空间为 LOG=18 覆盖所需跳跃层数。
- 允许不连通、重边、自环。森林中的孤立点也要被初始化。
- 跨连通分量先输出不可达,不调用路径查询函数。
- 本系列按
使用, NEG小于所有合法边权;mx的零初始化不能代替负无穷。 - 必须先读取当前段的信息,再移动顶点。先改
u再取mx[u][j],会漏掉原来的那一段。 - 相同点的返回值要遵循题目约定。本模板明确返回
,一般理论中不必为最大空集合定义一个数值。
负权与不可达检查
输入:
3 1
1 2 -5
3
1 2
1 3
3 3
输出:
-5
impossible
0
若把路径最大值的初值写成
9 练习
| 层次 | 题目 | 训练内容 |
|---|---|---|
| 最小化最大边 | luogu P2245 | 最小生成森林加倍增查询,注意重边、自环与不可达。 |
| 最大化最小边 | luogu P1967: [NOIP 2013 提高组] 货车运输 | 改用最大生成森林与路径最小值。 |
| 全树瓶颈 | luogu P2330: [SCOI2005] 繁忙的都市 | 先最小化选边数,再最小化最大边;理解 MST 可以给出最优瓶颈,但反向结论不成立。 |
下一篇 严格次小生成树 继续使用树上路径信息,决定加入一条非树边后应删除哪条边。
10 相关题解
暂无相关题解