题解：AT_abc416_e [ABC416E] Development

Chen78999 · 2025-07-27 14:33:34 · 题解

题意简述

给定一张无向图，有 N 个点和 M 条边，每条边都有一个正的代价。此外，还有 K 个点有机场，可以用 T 的代价从任何一个有机场的点到另一个有机场的点。现在有三种操作：

1. 加边。
2. 在指定点上建设机场。
3. 求所有可达点对的最少代价之和。

我们需要处理所有 Q 个操作，并输出所有第三种操作的结果。

朴素做法

如果我们每遇到一次 3 操作就用 Floyd 求一次全源最短路，那么最坏复杂度为 {\color{red}O(N^3Q)}，代入题目中变量 N \le 500，Q \le 1000 后，计算得 N^3Q = 1.25 \times {10}^{11}，显然无法通过。

所以我们必须考虑优化。

优化

我们可以先考虑操作较少的情况。

没有加边操作和机场的情况

这时，我们可以预先用 Floyd 求一遍最短路并求和，然后可以 O(1) 回答每个询问，时间复杂度为 O(N^3+Q)。

有加边操作的情况

同样地，我们可以预先用 Floyd 求一遍所有点对间的最短路。

当 x 和 y 之间添加了一条代价为 t 的边时，i 和 j 之间的最少代价就会变成以下其中之一：

• 从 i 出发到达 x，然后通过新边到达 y，最后到达 j 的代价；
• 从 i 出发到达 y，再经过新边到达 x，然后到达 j 的代价；
• 保持不变。

所以此时我们可以先用 O(N^3) 预处理，然后 O(N^2) 处理每个询问，时间复杂度为 O(N^3+N^2Q)。

有加边操作和机场的情况

如果每个城市都有机场，那么最多可以得到 N^2 条边。如果每建一个机场，就在所有有机场的城镇之间添加边，并重新计算最少代价，总共需要 O(N^2) 时间，总时间复杂度将达到 O({\color{red}N^4}+N^2Q)，无法通过。即使等到操作 3 再执行 Floyd 算法，情况也是一样。

正解

我们注意到，可以维护每个节点到最近机场的最少代价，第 i 号节点到最近机场的最少代价记作 A_i。如果从第 i 号节点无法到达任何一个机场，则 A_i = +\infty。

这样对每个加机场的操作，我们只需要 O(N) 更新每个点到最近有机场城市的最少代价即可。

:::::warning[注意]{open} 对于每个加边操作，加边完成后也要更新每个点到最近有机场城市的最少代价。对应代码95-102行。

::::info[例子] 考虑以下情况：

一共有 4 个顶点，从第一个点到第二个点代价为 1，从第二个顶点到第三个顶点代价为 100。