A90630 RAILWAY CONSTRUCTION 题解 定义与记号 为方便起见，我们先定义： * dis[u]：节点 1 到节点 u 的最短路长度，称为节点 u 的"距离"。 * 若 dis[u] > dis[v]，称节点 u 比节点 v 更深。 * 若 dis[u] < dis[v]，称节点 u 比节点 v 更浅。 * u -> v：表示从 u 到 v 的一条有向边。 * u --> v：表示从 u 到 v 的一条任意路径。 * 两条路径相交：当且仅当它们经过至少 1 个相同的节点。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 几个基本事实 1. 新边只能从更浅的点出发：因为所有边权为正，且不能改变任何点的最短路距离，所以对任意节点 u，只能从 dis 严格小于 dis[u] 的节点出发建边。特别地，我们总可以加边 1 -> u，但永远不能加边 u -> 1。 2. 只需考虑最短路 DAG：既然不能改变最短距离，且列车只走最短路，那么原本不在最短路上的边，无论怎么加新边，它都不会出现在任何最短路上。因此我们先跑一遍最短路，只保留最短路上的边，得到的新图是一个 DAG（有向无环图），其拓扑序就是节点距离的升序。后续讨论都在这个 DAG 上进行。 3. 每个非源点至少需要 2 条入边：加完所有新边后，除节点 1 外的每个节点必须有至少 2 条入边。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 核心引理 > 引理：如果除节点 1 外每个节点恰好有 2 条入边，则图就满足题意（即对每个 v 存在两条从 1 到 v 的内部点不相交的最短路）。 证明（数学归纳法）： 对任意节点 u，假设所有距离比 u 小的节点都已满足条件，只需证明 u 也满足。设 u 的两条入边分别来自 s 和 t。 情况一：s 或 t 是节点 1。 直接选 1 --> s -> u 和 1 --> t -> u 这两条路径，显然不相交，满足条件。 情况二：s 和 t 都不是节点 1。 * 任取一条路径 1 --> s，称为 path 0。 * 由归纳假设，到 t 存在两条内部不相交的路径 path 1 和 path 2。 如果 path 0 与 path 1（或 path 2）不相交，直接选 path 0 + s -> u 和 path 1 + t -> u 即可。 所以只需处理 path 0 同时与 path 1 和 path 2 都相交 的情况： * 找到 path 0 与 path 1 或 path 2 相交的最浅节点 a 和最深节点 b。 * 若 a、b 都是 path 0 与 path 1 的交点：选路径 1 -> a -> (沿 path 1) -> b -> s -> u 和 path 2 + t -> u。 * 否则（a 和 b 分别在不同路径上）：选路径 1 -> a -> t -> u 和 1 -> b -> s -> u。 两种情况都满足条件。引理证毕。 ∎ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 算法思路 由引理可知，只需让每个非源点至少有 2 条入边即可。 O(NQ) 基础做法 对于固定的 w 数组： 1. 在最短路 DAG 中，找出所有只有 1 条入边的节点，记录其唯一入边的起点。 2. 按距离升序扫描所有节点，维护一个数组 val，记录前面出现过的 w 的最小值和次小值（实际上只需维护下标）。 3. 贪心加边：对每个只有 1 条入边的节点，从前面 w 最小的节点向它连一条新边，代价为该点的 w。 对固定 w 计算一次答案只需 O(n)，所以总复杂度 O(nq)。 O((N+Q) LOG N) 优化 为了加速，我们尝试在 w 变化时动态维护 val 数组。关键技巧是：将所有修改操作反序处理，即只考虑 w 递减的情况。 根据 val 数组的值，可以将序列分成若干子段（subsegment），用 std::set 维护这些子段。每次 w_k 减小时，它会影响 val 的一个后缀，我们找到这个后缀，然后逐段更新 val，直到 w_k 大于当前子段的次小值为止。 对每个子段的更新操作分三类： 1. w_k 恰好是子段的最小值：此操作可能多次发生，但不会改变 val，可以用线段树一次性处理。每次修改至多做 1 次。 2. w_k 恰好是子段的次小值：由于不同子段的次小值互不相同，每次修改也至多做 1 次。 3. w_k 既不是最小值也不是次小值：每执行一次（除第一次外）都会使子段数量减少 1，因此这类操作总共不超过 n + q 次。 用 std::set + 线段树，每个操作可以在 O(log n) 内完成。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总复杂度 O(mlogm+(n+q)logn)O(m log m + (n + q) log n) O(mlogm+(n+q)logn) 其中 mlog⁡mm \log mmlogm 来自 Dijkstra 建最短路 DAG，(n+q)logn(n+q) log n(n+q)logn 来自动态维护 val 数组的过程。