双权瓶颈路径

每条边有两个权值 (a,b),最小化路径上 max a + max b;按 a 扫描,用按 b 的 MST 回答瓶颈。

标签 图论 / 瓶颈路径 / 生成树 / 动态 MST

模型

给定无向图 𝐺=(𝑉,𝐸),每条边 𝑒 有两个权值 𝑎𝑒,𝑏𝑒,以及起点 𝑠 和终点 𝑡。对一条路径 𝑃,记

𝐴(𝑃)≝max𝑒∈𝑃𝑎𝑒,𝐵(𝑃)≝max𝑒∈𝑃𝑏𝑒

要求

min𝑃:𝑠→𝑡(𝐴(𝑃)+𝐵(𝑃))

路径可以只考虑简单路径。目标不是最小化边权和,而是最小化两个瓶颈值之和。

阈值扫描

固定 𝐴0,只保留满足 𝑎𝑒≤𝐴0 的边,得到子图 𝐺𝐴0。记 𝐵(𝐴0) 为 𝐺𝐴0 中 𝑠 到 𝑡 的所有路径里最小的 𝐵(𝑃)。那么

min𝑃(𝐴(𝑃)+𝐵(𝑃))=min𝐴0(𝐴0+𝐵(𝐴0))

其中 𝐴0 只需要取某些边的 𝑎 值。

固定 𝐴0 后,𝐵(𝐴0) 就是一个普通的最小瓶颈路径问题。无向图中,任意一棵最小生成树都是最小瓶颈生成树,所以:

  • 对 𝐺𝐴0 按 𝑏 求最小生成森林;
  • 若 𝑠,𝑡 连通,𝐵(𝐴0) 就是森林中 𝑠 到 𝑡 路径上的最大 𝑏;
  • 若 𝑠,𝑡 不连通,则 𝐵(𝐴0)=∞。

事件和扫描模型

用事件模型和扫描模型的记号。取事件集为边集 𝐸,事件 𝑒 表示加入边 𝑒。偏序由

𝑒⪯𝑓当且仅当𝑎𝑒<𝑎𝑓或𝑒=𝑓

给出,取线性扩展

ℓ:𝐸→𝑇={1,…,𝑚}.

令 𝑆 为 𝐺 的所有生成森林,𝐹0=∅。对 𝐹∈𝑆 与 𝑒={𝑢,𝑣}∈𝐸,若 𝑢,𝑣 在 𝐹 中连通,令 𝑔 为 𝐹+𝑒 的唯一环上一条 𝑏 最大的边,定义

𝑈(𝑒,𝐹)≝{𝐹∪{𝑒}端点不连通(𝐹∪{𝑒})∖{𝑔}端点连通且𝑏𝑔>𝑏𝑒𝐹否则

于是事件模型为

ℰ︀=(𝐸,⪯,𝑈,ℓ).

令 𝑒𝜏=ℓ−1(𝜏),𝑢𝜏(𝐹)=𝑈(𝑒𝜏,𝐹),𝐹𝜏=𝑢𝜏(𝐹𝜏−1)。对 𝑎 的不同取值 𝐴1<…<𝐴𝑁,令

𝜏𝑗=max{ℓ(𝑒):𝑎𝑒≤𝐴𝑗},𝑞𝑗=(𝜏𝑗,𝑄𝑗),

其中 𝑄𝑗:𝑆→ℝ∪{+∞} 定义为

𝑄𝑗(𝐹)≝{𝐴𝑗+max𝑒∈𝑃𝑠,𝑡(𝐹)𝑏𝑒𝑠与𝑡在𝐹中连通+∞否则

𝑃𝑠,𝑡(𝐹) 为 𝐹 中 𝑠 到 𝑡 的路径。依赖集为

𝐷𝑞𝑗={𝑒:𝑎𝑒≤𝐴𝑗}.

于是扫描模型为

ℳ︀=(𝑇,𝑆,𝐹0,(𝑢𝜏)𝜏∈𝑇,(𝜏𝑗,𝑄𝑗)𝑗=1𝑁),

原问题的答案为 min𝑗=1𝑁𝑄𝑗(𝐹𝜏𝑗)。

动态 MST

把边按 𝑎 升序排序,依次加入。维护当前子图按 𝑏 的最小生成森林:

  • 若新边的两个端点不连通,直接加入;
  • 若已经连通,查询两点路径上 𝑏 最大的边。如果这条边的 𝑏 比新边大,就删掉它并加入新边,否则丢弃新边。

这是只在加边时发生的动态 MST,用 LCT 维护路径最大边即可。每加入一条边后,如果 𝑠,𝑡 连通,就用当前边的 𝑎 加上路径上的最大 𝑏 更新答案。

正确性

设最优路径为 𝑃∗,取 𝐴0=𝐴(𝑃∗)。此时 𝑃∗ 的所有边都在 𝐺𝐴0 中,所以 𝐵(𝐴0)≤𝐵(𝑃∗),算法得到的值不会超过最优值。

反过来,对任意 𝐴0,𝐴0+𝐵(𝐴0) 都对应 𝐺𝐴0 中一条真实路径的代价,因此不会小于最优值。两边夹住,扫描得到的即是最小值。

复杂度

排序 𝑂(𝑚log𝑚);LCT 每次加边、查询和替换均为均摊 𝑂(log𝑛)。总复杂度 𝑂(𝑚log𝑚+𝑚log𝑛),空间 𝑂(𝑛+𝑚)。

变式

把目标换成 minmax(𝐴(𝑃),𝐵(𝑃)) 或 min(𝐴(𝑃)+𝑘𝐵(𝑃)) 时,仍然可以按 𝐴 扫描,只是用路径上的最大 𝑏 计算候选答案。若交换 𝑎,𝑏 的角色,则改为按 𝑏 扫描、维护按 𝑎 的 MST。

这个模型的关键是“固定一个瓶颈,另一个瓶颈由 MST 回答”,不要和普通的边权和最短路或最小差值生成树混淆。

源码位置