[NOI2014] 魔法森林

双权瓶颈路径:最小化路径上 max a + max b;按 a 排序,用 LCT 动态维护按 b 的 MST。

来源 Luogu NOI 2014 P2387 · 标签 双权瓶颈路径 / 生成树 / LCT / 动态 MST

题目描述

给定一张 𝑛 个点、𝑚 条边的无向图,每条边有两个权值 𝑎𝑖,𝑏𝑖。小 E 从 1 号点出发,要到 𝑛 号点。

如果携带 𝐴 个 A 型守护精灵和 𝐵 个 B 型守护精灵,那么可以经过边 𝑖 当且仅当 𝐴≥𝑎𝑖 且 𝐵≥𝑏𝑖。求能够从 1 到达 𝑛 的最小 𝐴+𝐵。

图可能有重边和自环。若无法到达,输出 -1。

2≤𝑛≤5×104,0≤𝑚≤105,1≤𝑎𝑖,𝑏𝑖≤5×104。

题解

对一条路径 𝑃,需要携带的数量是

max𝑒∈𝑃𝑎𝑒+max𝑒∈𝑃𝑏𝑒

这是 双权瓶颈路径 的具体实例。

把边按 𝑎 升序排序,依次加入,维护当前边集按 𝑏 的最小生成森林。设当前加入边的 𝑎 为 𝐴。

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

如果 1 和 𝑛 连通,查询它们路径上的最大 𝑏,用 𝐴 加这个最大值更新答案。因为所有已加入边的 𝑎 都不超过 𝐴,所以这个候选值对应一条合法路径。

实现上用 LCT 维护动态最小生成森林。把每条边拆成一个带权点,路径查询返回 𝑏 最大的边节点,替换时断开该边节点与两个端点的连接。自环不会改变连通性,直接跳过。

复杂度

排序为 𝑂(𝑚log𝑚),每条边最多触发一次 LCT 的查询、断边和连边,总复杂度 𝑂(𝑚log𝑚+𝑚log𝑛),空间 𝑂(𝑛+𝑚)。

源码位置