冯梓轩集训总结3——最短路

模版算法

Dijkstra

可以说是最常用的最短路算法了。主要思想是找到当前更新过的距离源点最近的点，然后用它的最短路去更新与它相连的点的最短路。对于距离源点最近，可以开一个小根堆维护，这样的时间复杂度为 \(O(m \log m)\)。

但是算法有一个弊端：所有边的边权必须不为负，否则出现负权时会破坏之前的扩散过程。不过从其他同学那里得到了一些启发：带有负权的图，可以先跑一遍 Dijkstra，遇到负权边就不继续往下更新，这样可以节约一些跑非负权的时间。

Bellman-Ford

基于一个原则：一个人如果不知道源点到自己的最短路，就去问他的邻居，如果邻居也不知道就继续问，如此循环往复，直到到达源点就能知道，这称为松弛操作。由于最短路在没有负环的时候最多经过 \(n\) 个点，所以只需进行 \(n-1\) 轮松弛即可求得最短路，时间复杂度为 \(O(nm)\)。基于其原理，如果 \(n-1\) 轮松弛完毕后还能进行松弛操作，说明图中存在负环。

队列优化——SPFA

可以发现一轮松弛中有很多冗余操作。只有当一个点被松弛成功时，它才可能去松弛其他点。基于此，可以开一个队列维护可以松弛其他点的点，如果一个点不在队列中且被松弛成功就入队。这样的时间复杂度在随机数据下表现非常好，甚至可能比 Dijkstra 还好，但是由于其本质，还是有可能到达理论上限 \(O(nm)\)，例如菊花套网格图、外挂诱导节点等就可以卡掉。SPFA 有很多种优化，但是可以一一对应被卡掉。这里说一个有一点实际用处的做法：如果要找负环的话，优先用栈跑 SPFA，这样 有可能 是找负环的速度加快。不过不要用它来跑普通最短路，因为可以外挂诱导节点，使它一直往局部最优走，最后才发现不是最短的。

Floyd

看起来不起眼，但实际上可以魔改。

设 \(f_{k,i,j}\) 表示只用前 \(k\) 个点进行更新，得到的 \(i\) 到 \(j\) 的最短路长度。方程为：

\[f_{k,i,j} = \min \{ f_{k-1,i,j}, f_{k-1,i,k} + f_{k-1,k,j} \} \]

发现可以将第一维滚掉，得到新方程：

\[f_{i,j} = \min \{ f_{i,k} + f_{k,j} \} \]

这样做的时间复杂度为 \(O(n^3)\)。如果只跑最短路，那确实是一种较劣的方法，但由此算法可以方便的解决一些其他问题。

判负环

由于负环上的点的最短路会绕回自己，且长度为负，所以图中存在负环的判断条件即为：\(f_{i,i} < 0\)。

找最小环（不包括二元环）

最小环可以拆成三部分：一条边、另一条边，和一条不经过这两条边的路径。

具体实现时，在用 \(k\) 更新 \(i\) 到 \(j\) 的最短路前，先用 \(f_{i,j} + w_{i \to k} + w_{j \to k}\) 更新最小环的长度，再更新最短路的长度。由于先前的 \(f_{i,j}\) 是由前 \(k-1\) 个点作为中转的，没有经过 \(k\)，遂可以保证当前 \(i\) 到 \(j\) 的最短路不会经过与 \(k\) 相连的边，正好是一个点数大于 \(2\) 的环。

传递闭包

连通性问题。设 \(f_{i,j} = 0 / 1\) 表示 \(i\) 与 \(j\) 联通\(/\) 不连通。方程显然为：

\[f_{i,j} \mid= f_{i,k} \& f_{k,j} \]

由于只有 \(0,1\)，可以考虑使用 bitset 优化，时间复杂度为 \(O(\frac{n^3}{w})\)。

有边数限制的最短路

刷题时遇到的一种题，感觉很妙。

设 \(f_{l,i,j}\) 表示从 \(i\) 到 \(j\) 经过 \(l\) 条边的最短路。方程即为：

\[f_{l,i,j} = \min \{ f_{p,i,k} + f_{l-p,k,j} \} \]

设最大边数限制为 \(q\)，上述算法的时间复杂度为 \(O(n^3q^2)\)。但其实这是可以优化的。

与最小环类似，可以将一条路径拆成前一段路径与最后一条边。由于 最短路一定是由其他点的最短路更新的，所以这样做与前一个算法效果等价。方程为：

\[f_{l,i,j} = \min \{ f_{l-1,i,k} + f_{1,k,j} \} \]

时间复杂度变为 \(O(n^3q)\)。

例题

神秘力量

开始想了一个自己认为很对的做法：既然一个点只要不育另一个点直接相连就能更新它，那我就开一个带权并查集，记录一下与节点 \(i\) 不直接相连的最短的最短路长度。每次用一个 \(u\) 去更新 \(v\) 时，先不将 \(u\) 的最短路加入并查集，用上一步的并查集去更新，待把所有的 \(v\) 更新完后，再将 \(u\) 加入并查集。待是这样做是有问题的：如果图不是一个连通图，本来与一个点不连通的图经过特殊边也是可以飞过去的，但是用并查集的话不连通的点就无法更新。

本题要使用补图技术。一个点如果与另一个点不直接相连，那么在补图上它们就直接相连，用 \(0\) 费更新时，更新在补图上与这个点相邻的点即可。但是补图的数量级最坏时 \(O(n^2)\)的，所以不能直接建出来。

这里要利用 Dijkstra 的性质：堆顶元素的最短路长度一定是当前最短的。这样，当一个点被另一个点 \(0\) 费更新后，由于其余最短路都比堆顶大，就不会被其余的更新。我们可以开一个 \(set\)，记录一下当前没有被 \(0\) 费更新过的点，取出堆顶时遍历 \(set\)，如果不与堆顶节点直接相连就更新，并将其移出 \(set\)。由于堆顶最小，所以不与堆顶节点直接相连的点一定会被更新，且之后不会再次访问，时间复杂度得到保证。

传送卷轴

此题要用到一个重要技术：虚点。

如果对每对节点暴力建边的话，时间复杂度为 \(O(n^2)\)，无法接受。我们可以考虑对深度分层，对每一个深度建一个中转点，与深度等于它的点连双向边，再跑最短路，这样看貌似是对的，但是同层的节点就有可能 \(0\) 费相互到达，这样是错的。所以我们将中转点拆成一个入点和一个出点，满足深度要求的出点向入点连边，然后入点向其对应深度的原节点连边，原节点向其对应深度的出点连边，这样就解决了问题，并且优化了时间复杂度。

全局第K短路

一个重要性质：第 \(k\) 短路的长度最长为第 \(k\) 小的边权，正确性显然。利用这个性质，我们将边按边权递增排序，并取出前 \(k\) 短的边，对取出的每一个点跑最短路，用大根堆维护 \(k\) 短路。这样下来，最终要跑最短路的点数为 \(O(k)\)，边数也为 \(O(k)\)，遂时间复杂度为 \(O(k^2 \log k)\)。由于 \(k \leq 400\)，遂可以通过。

期望最短路——果国的奇妙旅行

显然，期望状态倒着设。设 \(f_i\) 表示从 \(i\) 到 \(n\) 的最小期望票数，方程即为：

\[f_{u} = (\sum\limits_{i=1,u \to v}^{l_u} \frac{f_v}{d_u}) + \frac{d_u - l_u}{d_u} \times f_u + 1 \]

这里的 \(l_u\) 表示选择走的点的数量，\(\sum\limits_{i=1,u \to v}^{l_u} \frac{f_v}{d_u}\) 表示抽到了到 \(v\) 的票并且选择走过去，由于抽到每张票的概率为 \(\frac{1}{d_u}\)，乘上 \(v\) 到 \(n\) 的期望票数就是经过 \(v\) 的期望票数。\(\frac{d_u - l_u}{d_u} \times f_u\) 表示抽到了票但是不走的期望票数，最后加一表示选择之前先抽一张票。这是一个方程，最终化简得：

\[f_{u} = \frac{(\sum\limits_{i=1, u \to v}^{l_u} f_v) + d_u}{l_u} \]

但是我们并不确定 \(u\) 是否会选择去一个 \(v\)。注意到求的是最小期望，所以若加入 \(v\) 能使 \(f_u\) 变小，就将其加入。由于在加入之前的 \(l_u\) 可以看作一个定值，所以分子部分一定是先加入小的再加入大的，这符合最短路的特征，可以使用最短路求解。这可以算是魔改版的最短路。