全面解析多源最短路算法与Bitset状态压缩优化

核心逻辑与数学原理

多源最短路（All-Pairs Shortest Paths, APSP）的目标是求解图中任意两点 $u, v \in V$ 之间的最短路径。针对这一问题，Floyd-Warshall 算法在动态规划的框架下展现了极其精炼的矩阵代数本质。同时，在无权图或传递闭包问题中，结合 Bitset 状态压缩可以将算法常数压制到物理极限。

1. 矩阵增量范式：Floyd-Warshall 算法

Floyd 算法的本质是拓扑中间节点的动态引入。

• 数学原理：定义状态矩阵 $f[k][i][j]$，表示允许经过的最大节点编号为 $k$ 的情况下，从节点 $i$ 到节点 $j$ 的最短路径长度。
• 矩阵递推：每一轮外层循环 $k$ 的引入，本质上是在原有的路径代数矩阵上，叠加了一个通过节点 $k$ 进行中转的全新拓扑空间。当 $k$ 从 $1$ 遍历到 $N$ 完毕后，空间中所有的中转路径可能性均被穷举。
• 复杂度定理：算法的空间复杂度通过滚动数组可以优化至 $O(N^2)$，时间复杂度严格为 $O(N^3)$。由于其内存访问具有高度的局部连续性，极其有利于 CPU 高速缓存（Cache）优化，常数极小。

2. 传递闭包与 Bitset 状态压缩

在有向图的连通性判定（传递闭包）问题中，我们只关心 $i$ 是否能到达 $j$，状态矩阵退化为布尔矩阵 $f[i][j] \in \{0, 1\}$。

• 状态压缩原理：传统的布尔逻辑转移为 $f[i][j] = f[i][j] \lor (f[i][k] \land f[k][j])$。这意味着，当中间点 $k$ 确立，且 $i$ 能够到达 $k$ 时（即 $f[i][k] == 1$），节点 $i$ 的整行连通性状态 $f[i]$ 将直接叠加（按位或操作）节点 $k$ 的整行连通性状态 $f[k]$。
• 物理提速：使用 C++ std::bitset 替代传统的布尔数组，可以将连续的 64 个布尔值压缩进一个整型 CPU 寄存器中。通过单条指令执行 64 位并行位运算，将时间复杂度降低至真正的 $O(\frac{N^3}{w})$，其中 $w = 64$（在 64 位 Linux 评测机环境下）。

算法推导与状态设计

1. Floyd-Warshall 状态转移方程

定义 $d[i][j]$ 为存储距离的二维矩阵。在第 $k$ 轮迭代中，对于任意节点对 $(i, j)$，状态转移方程为：

$$d[i][j] = \min(d[i][j], d[i][k] + d[k][j])$$

物理边界：初始化时，若 $i == j$ 则 $d[i][j] = 0$；若存在直接有向边则 $d[i][j] = w(i, j)$；其余情况全部标定为 $\infty$。 循环顺序的硬性数学约束：阶段变量 $k$ 必须作为最外层循环。因为 $f[k][i][j]$ 的状态强依赖于 $f[k-1]$ 阶段的完全熟化状态。若将 $k$ 置于内层，则状态转移在中间点未完全就绪时发生，导致拓扑递推链断裂。

2. Bitset 传递闭包转移方程

定义 std::bitset<MAXN> g[MAXN]，其中 g[i][j] 表示 $i$ 能否到达 $j$。当外层循环控制变量 $k$ 确立时：

$$\text{if } (g[i][k]) \quad g[i] \mid= g[k]$$

物理含义：若 $i$ 可达 $k$，则所有 $k$ 能到达的点， $i$ 均可达。整行直接进行位或运算。

C++ 标准源码（Bitset 优化传递闭包工业模板）

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>

const int MAXN = 2005; // 针对 N <= 2000 强度的图论连通性设计

// 使用 bitset 压缩图的邻接矩阵和可达性矩阵
std::bitset<MAXN> g[MAXN]; 

void transitive_closure(int n) {
    // 致命低级错误防范：k 必须作为最外层循环，这是阶段驱动的核心
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            // 关键常数优化：只有当 i 确实能到达 k 时，整行位运算才有意义
            if (g[i][k]) {
                g[i] |= g[k]; // 单条机器指令并行处理 64 个点的状态转移
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    // 自环初始化
    for (int i = 1; i <= n; ++i) {
        g[i].set(i); // g[i][i] = 1
    }

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        g[u].set(v); // 有向边建立，g[u][v] = 1
    }

    transitive_closure(n);

    // 输出最终的可达性矩阵（0/1 连通状态）
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cout << (g[i][j] ? 1 : 0) << (j == n ? "" : " ");
        }
        std::cout << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. Floyd 算法三层循环顺序颠倒： 极其常见且低级的错误是将循环写成 for(i...) for(j...) for(k...)。这种写法在内层更新时，依赖的 d[i][k] 和 d[k][j] 本身还没有经过完全松弛，它们当前可能依然是初始的 $\infty$。这直接导致更新漏算，求出的最短路由于拓扑断层而比真实值偏大。必须铁律执行 k 在最外层。
2. Floyd 初始化未进行重边拦截： 在图的输入阶段，若题目给出的数据包含重边（即相同两点间有多条不同的边），选手若直接写 d[u][v] = w，会导致后续读入的、边权较大的重边覆盖掉之前读入的、更优的短边。标准读入必须写成 d[u][v] = \min(d[u][v], w)。

经典 NOIP/洛谷 真题

1. 洛谷 P1119 灾后重建

• 题意描述： 给出 $N$ 个村庄和 $M$ 条双向道路。每个村庄修复完毕的时间不同。有 $Q$ 个询问，每次询问在第 $t$ 天时，村庄 $x$ 到村庄 $y$ 的最短路径是多少。数据保证修复时间单调不降。
• 问题本质与核心思路： Floyd 算法动态增量特性的完美映射。传统的做法对于每次询问重跑算法显然会 TLE。注意到题目中“修复时间单调不降”，这与 Floyd 最外层循环 $k$ 的物理含义完美同构。我们可以维护一个全局的 Floyd 矩阵，不需要每次重跑。当读入一个询问 $(x, y, t)$ 时，利用双指针，将所有修复时间 $\le t$ 且之前未被引入的村庄作为中间点 $k$，执行最外层一轮的增量松弛更新。更新完毕后，矩阵中的 $d[x][y]$ 即为当前时点合法的最短路，时间复杂度优雅地被分摊在总计 $O(N^3 + Q)$ 内。

2. 洛谷 P2419 [USACO08JAN] Cow Contest S

• 题意描述： 有 $N$ 头奶牛进行比赛，给出了 $M$ 个胜负关系（形如 A 赢了 B）。假设比赛具有传递性（A赢B，B赢C $\implies$ A赢C）。求有多少头奶牛的最终排名是可以被完全确定的。
• 问题本质与核心思路： 利用传递闭包求解偏序关系的完备性。一头奶牛的准确排名能够被完全确定的充要条件是：它与其他所有奶牛的胜负关系都是确定的。也就是说，对于奶牛 $i$，其余任何一头奶牛 $j$（$j \neq i$），要么 $i$ 能到达 $j$（$i$ 赢 $j$），要么 $j$ 能到达 $i$（$j$ 赢 $i$）。核心思路：利用邻接矩阵建图，跑一次标准的 Bitset 传递闭包。结束后，统计每个节点 $i$，满足 (g[i][j] || g[j][i]) == true 的 $j$ 的数量。若该数量恰好为 $N - 1$，则该节点的排名可确定。总时间复杂度为极低的 $O(\frac{N^3}{64})$。