子图最短路 题解

题目分析

给定一个 $n$ 个结点、$m$ 条边的带权无向图。对于任意区间 $[\ell, r]$，定义子图 $G(\ell, r)$ 仅保留编号在区间内的结点和它们之间的边。题目要求所有子图中、所有满足 $\ell \le u \le v \le r$ 的无序点对 $(u, v)$ 的最短距离之和，若两点不连通则距离视为 $0$。答案需要对 $10^9$ 取模。

$n \le 100$ 较小，但若对 $O(n^2)$ 个子图分别建图跑最短路，复杂度会达到 $O(n^5)$ 左右，无法通过。我们需要利用子图随区间变化的特性来优化。

解题思路

核心观察：当固定左端点 $\ell$，让右端点 $r$ 从 $\ell$ 向右扫描时，子图会逐步加入编号更大的结点。这相当于我们依次插入新结点，并允许它作为中间结点来更新其他点对的最短距离。

这种“动态加点”的最短路更新正好可以使用 Floyd-Warshall 算法 的增量形式：每次加入一个新结点 $k$，尝试以 $k$ 为中间点对所有点对 $(i, j)$ 进行松弛操作：

这样，每次插入的代价仅为 $O(n^2)$，而不是重新运行整个 Floyd。

因此，我们可以枚举左端点 $\ell$，维护一个距离矩阵 $g$，并逐步加入 $r = \ell, \ell+1, \dots, n$。每加入一个 $r$ 后，$g$ 就恰好存储了子图 $G(\ell, r)$ 中所有点对的最短距离（不可达的点对距离会保持为初始的无穷大）。此时累加 $g[i][j]\ (\ell \le i \le j \le r)$ 即可。

为了处理题目中“不连通视为 $0$”的特殊要求，我们可以将无穷大设为一个恰好等于模数 $10^9$ 的值。这样一来，累加时无穷大会被加进答案，但取模后自动变为 $0$，非常巧妙。

算法说明

1. 初始化

   • 设 f[u][v] 表示 $u, v$ 之间的直接边权（取最小值以处理重边）。
   • 对角线 f[i][i] = 0，无边相连则 f[u][v] = INF。
   • 取 INF = 10^9（即题目模数）。

2. 枚举左端点 $\ell$
   对于每个 $\ell = 1 \dots n$：

   • 将全局边权矩阵 f 拷贝到工作矩阵 g 中。

     注意：g 包含所有 $1 \dots n$ 的结点，但我们将只用编号 $\ge \ell$ 的结点作为中间结点，因此 $<\ell$ 的结点不会参与松弛，子图外的结点不会影响区间内的最短路计算。

   • 用 $r$ 从 $\ell$ 到 $n$ 依次扩展右端点：
     • 插入结点 $r$：用 $r$ 作为中间结点，对任意 $i, j$ 执行 g[i][j] = min(g[i][j], g[i][r] + g[r][j])。
     • 累加答案：对于所有 $\ell \le i \le j \le r$，将 g[i][j] 累加到答案中，并对 $10^9$ 取模。

3. 输出答案

由于 $10^9$ 既是模数又是 INF，不可达的点对累加 INF 相当于加 $10^9$，模 $10^9$ 后贡献为 $0$，完美契合题意。

时间复杂度分析

• 外层 $\ell$ 循环：$O(n)$ 次。
• 内层 $r$ 循环：对于固定的 $\ell$，右端点从 $\ell$ 移动到 $n$，大约 $O(n)$ 次。
• 每次加入 $r$ 的松弛操作：双重循环遍历所有点对，$O(n^2)$。

因此总复杂度为 $O(n^4)$。对于 $n \le 100$，实际运算量约为 $\frac{n^4}{2} \approx 5\times 10^7$ 次基本运算，常数很小，可以在 1s 内轻松通过。

空间复杂度为 $O(n^2)$，存储两个邻接矩阵。

参考代码

下面是完整的 C++ 实现，并附有详细注释。

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 105;
6const int mod = 1e9;        // 模数，同时用作 INF
7const int INF = mod;
8
9int n, m;
10int f[N][N];                // 原始图的直接边权
11int g[N][N];                // 动态维护的最短距离矩阵
12int ans;
13
14int main() {
15    scanf("%d%d", &n, &m);
16
17    // 初始化邻接矩阵
18    for (int i = 1; i <= n; i++) {
19        for (int j = 1; j <= n; j++)
20            f[i][j] = INF;
21        f[i][i] = 0;
22    }
23
24    // 读入边，处理重边（取最小权值）
25    for (int i = 1; i <= m; i++) {
26        int u, v, w;
27        scanf("%d%d%d", &u, &v, &w);
28        f[u][v] = min(f[u][v], w);
29        f[v][u] = min(f[v][u], w);
30    }
31
32    // 枚举左端点 l
33    for (int l = 1; l <= n; l++) {
34        // 将原始边权拷贝至工作矩阵 g
35        for (int i = 1; i <= n; i++)
36            for (int j = 1; j <= n; j++)
37                g[i][j] = f[i][j];
38
39        // 扩展右端点 r
40        for (int r = l; r <= n; r++) {
41            // 将结点 r 作为中间结点，更新所有点对
42            for (int i = 1; i <= n; i++)
43                for (int j = 1; j <= n; j++)
44                    g[i][j] = min(g[i][j], g[i][r] + g[r][j]);
45
46            // 累加当前子图 G(l, r) 内所有点对的最短距离
47            for (int i = l; i <= r; i++)
48                for (int j = i; j <= r; j++)
49                    ans = (ans + g[i][j]) % mod;
50        }
51    }
52
53    printf("%d\n", ans);
54    return 0;
55}

代码细节说明

• INF 设为 mod (1e9)：边权最大为 $10^6$，最短路长度远小于 $10^9$，因此用 $10^9$ 表示无穷大是安全的。累加时，不可达点对的 g[i][j] 仍为 INF，加入答案后对 mod 取模即得 $0$，恰好满足题目“不连通视为 $0$”的要求。
• 中间结点的合法性：虽然 g 初始包含了所有编号的结点，但我们在松弛时只会用 $r \ge \ell$ 的结点作为中间点。编号小于 $\ell$ 的结点从未被用作中间点，因此它们不会影响区间内点对的最短距离，保证了子图的正确性。
• 重边处理：直接取 min 保留最小边权。

小结

本题巧妙地利用了 Floyd 算法的增量更新性质，将“静态区间子图最短路求和”转化为“动态加点并累加”的过程，从而将复杂度从 $O(n^5)$ 降至 $O(n^4)$，在 $n=100$ 的数据范围内完美运行。这种按编号顺序动态插入结点并维护全源最短路的技巧在一些动态图问题中都非常实用。