「APIO 2015」Jakarta Skyscrapers（BFS）

题目大意

「APIO 2015」Jakarta Skyscrapers（Luogu 3645）

有 $n$ 个位置，$m$ 只 doge，第 $i$ 只在位置 $b_i$ 上。一开始给 $1$ 号 doge 传达信息，第 $i$ 只 doge 在收到信息后，可以进行如下操作：

• 自己向左后向右移动 $p_i$ 个位置，花费 $1$ 个单位时间。
• 将携带的信息传达给在同一个位置上的 doge，花费 $0$ 个单位时间。

问信息传达给 $2$ 号 doge 所需要的最少时间。

数据范围：$n, m \le 3 \times 10^4$。

思路分析

最容易想到的是一个暴力算法：我们每次让 doge 向左或向右跳，碰到一个 doge 就传达信息。考虑对于每一个位置建一个点，每新来一个 doge 就对于每一个它能够跳到的位置新建一个辅助点。然后：

• 每个辅助点向对应位置的点连一条长度为 $0$ 的边。
• 从 $b_i$ 向 $b_i$ 的辅助点连一条长度为 $0$ 的边。
• 如果 doge 能够跳到位置 $x$，就从 $x$ 的辅助点向 $x - p_i$ 或 $x + p_i$ 的辅助点连长度为 $1$ 的边（取决于 $x$ 和 $b_i$ 的相对位置）。

不幸的是，我们发现这样的点数，边数都是 $O(nm)$ 的，无法通过此题。注意到我们的算法在 $p_i$ 较大的时候不会出现问题，而 $p_i$ 较小的时候的点数，边数较大。具体来讲，我们的点数是不超过 $n + \frac{nm}{P_0}$ 的，边数是不超过 $m + \frac{2mn}{P_0}$ 的，其中 $P_0$ 是所有 $p_i$ 的最小值。

那么，有没有在 $p_i$ 较小的时候可行的算法呢？发现 $p_i$ 较小的时候很多 doge 能跳到的位置集合都是完全相同的。也就是说，如果两个 doge $p_i$ 相同，$b_i \bmod p_i$ 同余，那么我们考虑将它们一起解决。对于每一个位置再建立 $P_1$ 个辅助点，其中 $P_1$ 是所有 $p_i$ 的最大值。我们记第 $i$ 个点的第 $j$ 个辅助点为 $\text{pnt}(i, j)$。建如下的图：

• 每个 $\text{pnt}(i, j)$ 向 $i$ 点连一条长度为 $0$ 的边。
• 每个 $\text{pnt}(i, j)$ 向 $\text{pnt}(i - j, j), \text{pnt}(i + j, j)$ 连长度为 $1$ 的边。
• 对于每个 doge，从 $b_i$ 向 $\text{pnt}(b_i, p_i)$ 连长度为 $0$ 的边。

经过计算，这个图的点数不超过 $n + P_1 \times n$，边数不超过 $2 P_1 \times n + m$。单独来看它还是 $O(nm)$ 的，但是我们可以将其与前一种建图方法结合起来。设定阈值 $\text{Bound}$，如果 $p_i > \text{Bound}$ 就使用第一种建图方法，否则使用第二种建图方法。这样图的点数不超过 $n + \text{Bound} \times n + \frac{nm}{\text{Bound}}$，边数不超过 $2n \times \text{Bound} + \frac{2nm}{\text{Bound}} + m$。发现 $\text{Bound} = \sqrt{m}$ 时最优，建完图后跑最短路即可。当然由于这个图的边权只有 $0, 1$，所以可以直接 BFS。时间复杂度 $O(\sqrt{m}(n + m))$。

代码实现

#include <cmath>