[NOI2014] 魔法森林
双权瓶颈路径:最小化路径上 max a + max b;按 a 排序,用 LCT 动态维护按 b 的 MST。来源 Luogu NOI 2014 P2387 · 标签 双权瓶颈路径 / 生成树 / LCT / 动态 MST
题目描述
给定一张 个点、 条边的无向图,每条边有两个权值 。小 E 从 号点出发,要到 号点。
如果携带 个 A 型守护精灵和 个 B 型守护精灵,那么可以经过边 当且仅当 且 。求能够从 到达 的最小 。
图可能有重边和自环。若无法到达,输出 -1。
,,。
题解
对一条路径 ,需要携带的数量是
这是 双权瓶颈路径 的具体实例。
把边按 升序排序,依次加入,维护当前边集按 的最小生成森林。设当前加入边的 为 。
- 若新边的两个端点不连通,直接加入;
- 若已经连通,查询两点路径上 最大的边。如果这条边的 大于新边的 ,就删掉最大边并加入新边,否则丢弃新边。
如果 和 连通,查询它们路径上的最大 ,用 加这个最大值更新答案。因为所有已加入边的 都不超过 ,所以这个候选值对应一条合法路径。
实现上用 LCT 维护动态最小生成森林。把每条边拆成一个带权点,路径查询返回 最大的边节点,替换时断开该边节点与两个端点的连接。自环不会改变连通性,直接跳过。
复杂度
排序为 ,每条边最多触发一次 LCT 的查询、断边和连边,总复杂度 ,空间 。