双权瓶颈路径
每条边有两个权值 (a,b),最小化路径上 max a + max b;按 a 扫描,用按 b 的 MST 回答瓶颈。标签 图论 / 瓶颈路径 / 生成树 / 动态 MST
模型
给定无向图 ,每条边 有两个权值 ,以及起点 和终点 。对一条路径 ,记
要求
路径可以只考虑简单路径。目标不是最小化边权和,而是最小化两个瓶颈值之和。
阈值扫描
固定 ,只保留满足 的边,得到子图 。记 为 中 到 的所有路径里最小的 。那么
其中 只需要取某些边的 值。
固定 后, 就是一个普通的最小瓶颈路径问题。无向图中,任意一棵最小生成树都是最小瓶颈生成树,所以:
- 对 按 求最小生成森林;
- 若 连通, 就是森林中 到 路径上的最大 ;
- 若 不连通,则 。
事件和扫描模型
用事件模型和扫描模型的记号。取事件集为边集 ,事件 表示加入边 。偏序由
给出,取线性扩展
令 为 的所有生成森林,。对 与 ,若 在 中连通,令 为 的唯一环上一条 最大的边,定义
于是事件模型为
令 ,,。对 的不同取值 ,令
其中 定义为
为 中 到 的路径。依赖集为
于是扫描模型为
原问题的答案为 。
动态 MST
把边按 升序排序,依次加入。维护当前子图按 的最小生成森林:
- 若新边的两个端点不连通,直接加入;
- 若已经连通,查询两点路径上 最大的边。如果这条边的 比新边大,就删掉它并加入新边,否则丢弃新边。
这是只在加边时发生的动态 MST,用 LCT 维护路径最大边即可。每加入一条边后,如果 连通,就用当前边的 加上路径上的最大 更新答案。
正确性
设最优路径为 ,取 。此时 的所有边都在 中,所以 ,算法得到的值不会超过最优值。
反过来,对任意 , 都对应 中一条真实路径的代价,因此不会小于最优值。两边夹住,扫描得到的即是最小值。
复杂度
排序 ;LCT 每次加边、查询和替换均为均摊 。总复杂度 ,空间 。
变式
把目标换成 或 时,仍然可以按 扫描,只是用路径上的最大 计算候选答案。若交换 的角色,则改为按 扫描、维护按 的 MST。
这个模型的关键是“固定一个瓶颈,另一个瓶颈由 MST 回答”,不要和普通的边权和最短路或最小差值生成树混淆。