你真的懂 Floyd 吗

Floyd 求最短路，时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。

1
2
3

for (int k = 1;k <= n;++k)
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= n;++j) dis[i][j] = min (dis[i][j],dis[i][k] + dis[k][j]);

【Q1】该算法的正确性？

算法基于动态规划。设 $f_{k,i,j}$ 表示只能借助于 $1,2,\cdots,k$ 点时，$i \to j$ 的最短路径。那么根据是否经过 $k$ 点，可以列出状态转移方程：

$f_{k,i,j} = \min (f_{k - 1,i,j},f_{k - 1,i,k} + f_{k - 1,k,j})$

很好理解，后者相当于以 $k$ 作为中转站，即 $i \to k \to j$ 的转移。那么当处理询问 $u,v$ 时，$f_{n,u,v}$ 即为所求。

可以发现 $f_{k,i,j}$ 只对 $f_{k - 1,i’,j’}$ 产生依赖，不难想到可以滚动数组优化。那么，Floyd 最终直接删去那一维，这样做不会出错吗？

现在我们去掉第一维，只要保证在转移时方程右侧的 $f_{i,j},f_{i,k},f_{k,j}$ 都是未被覆盖过的即可。当最外层为第 $k$ 次循环时，显然 $f_{i,j}$ 还未被覆盖。对于 $f_{i,k},f_{k,j}$，按照之前的三维转移方程，可以得到 $f_{k,i,k} = \min (f_{k - 1,i,k},f_{k - 1,i,k} + f_{k - 1,k,k}) = f_{k - 1,i,k}$，$f_{k,j}$ 同理。因此我们证明了空间优化的该算法的正确性。

与此同时，从动态规划的角度出发，“为什么 $k$ 循环需要放在最外层？”也就很好理解了。

【Q2】若每次修改一条边的权值，有必要重新完整的去做一遍 Floyd 算法吗？

答案是否定的，只需要 $O(n^2)$ 即可实现局部更新。设 $(u,v)$ 的权值更新为 $w(u,v)$（无向图），则可得到转移方程：

$f_{i,j} = \min (f_{i,j},\min (f_{i,u} + w(u,v) + f_{v,j},f_{i,v} + w(v,u) + f_{u,j}))$

例题：

Another Exercise on Graphs (easy version)
Another Exercise on Graphs (hard version)

解析：

根据边权排序，然后答案显然就是某一条边的值。当枚举到第 $i$ 条边的时候，比其小的边均置为 $0$，否则为 $1$。若 $i \to j$ 的最短路是 $w_i$，那么第 $i + 1$ 大的便是这条边。

进一步的，$\texttt{E2}$ 的 $m$ 很大，可是我们会发现有效的更新只有 $n - 1$ 次，因为之后 $(i,j)$ 的最短路已经为 $0$，不会再发生变化，并查集维护即可。

【Q3】变式 $1$ 【模板】传递闭包

简单来说，如果原关系图上有 $i$ 到 $j$ 的路径，则其传递闭包的关系图上就应有从 $i$ 到 $j$ 的边，均用 $0/1$ 表示。因此枚举中转点 $k$，若 $(i,k)$ 与 $(k,j)$ 均有连边，则可将 $(i,j)$ 连边。写成表达式，就是：

$f_{i,j} = \max (f_{i,j},\min (f_{i,k},f_{k,j}))$

【Q4】变式 $2$ [USACO07NOV] Cow Relays G 本质同 Walk

设 $A$ 中是经过 $x$ 条边的最短路，$B$ 中是经过 $y$ 条边的最短路。通过以下转移后，可以发现 $C$ 中是经过 $x + y$ 条边的最短路：

$C_{i,j} = \min ({C_{i,j}},A_{i,k} + B_{k,j})$

这样我们的转移就变得简单，重载后直接通过矩阵快速幂即可解决问题。

进一步的变式 [SCOI2009] 迷路，衡量距离。拆点与 bitset 的优化，时间复杂度 $O(\frac{n^3}{64} \log k)$。具体来说，对于一个点，拆成 $v_1 \sim v_{10}$，然后 $u \to v$ 一条边为 $w$ 的边，然后 $v_i \to v_{i - 1}$ 进行连边，于是可以变为 $u \to v_w$。