固定左端点 ℓ,让右端点 r 从 ℓ 一路长到 n;每加入一个点 k,就用 k 作中间点补一次 Floyd 松弛,并把子图 G(ℓ, k) 的点对距离全部累加。
给定包含 n 个结点 m 条边的带权无向图 G,结点依次以 1, 2, …, n 编号。第 i(1 ≤ i ≤ m)条边连接编号为 uᵢ 与 vᵢ 的两个结点,权值为 wᵢ。
对于指定的 1 ≤ ℓ ≤ r ≤ n,按以下方式构造图 G 的子图 G(ℓ, r):
G 中编号在区间 [ℓ, r] 中的结点。删去其它编号不在 [ℓ, r] 中的结点以及与之相连的边。剩余的结点和边构成子图 G(ℓ, r)。对于 G(ℓ, r) 中的任意结点 u, v 应有 ℓ ≤ u, v ≤ r。记 u, v 在子图 G(ℓ, r) 上的最短距离为 d(ℓ, r, u, v)。特殊地,若 u, v 在子图 G(ℓ, r) 上不连通,则认为 d(ℓ, r, u, v) = 0。
你需要求出 Σℓ=1…n Σr=ℓ…n Σu=ℓ…r Σv=u…r d(ℓ, r, u, v) 对 10⁹ 取模的结果。
l 使用了特殊写法 ℓ,以避免英文字母 l 与数字 1 混淆。第一行,两个正整数 n, m,表示结点数与边数。
接下来 m 行,第 i(1 ≤ i ≤ m)行包含三个正整数 uᵢ, vᵢ, wᵢ,表示一条连接结点 uᵢ, vᵢ 的权值为 wᵢ 的边。
输出一行,一个整数,表示上述四重求和对 10⁹ 取模的结果。
3 2 1 2 1 2 3 2
输出:
9
4 6 1 2 100 2 3 100 3 4 100 1 3 10 2 4 10 1 4 1
输出:
784
对于 40% 的测试点,保证 2 ≤ n ≤ 20。
对于所有测试点,保证 2 ≤ n ≤ 100,2 ≤ m ≤ n(n−1)/2,1 ≤ uᵢ, vᵢ ≤ n,1 ≤ wᵢ ≤ 10⁶。图中可能存在重边。
G(ℓ, r)。u, v 都有一个最短距离;不连通就记 0。u = v 的距离恒为 0,加了也白加,所以只统计 u < v;② "不连通记 0"意味着这些点对直接当作 0 贡献,不需要任何特判。O(n⁵) ≈ 10¹⁰,必定超时。带权无向图诱导子图全源最短路四重求和增量 Floyd重边取最小
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 m 行每行 u、v、w |
| 输出 | 四重求和对 10⁹ 取模 |
| 数据范围 | 2 ≤ n ≤ 100,2 ≤ m ≤ n(n−1)/2 |
| 边权 | 1 ≤ wᵢ ≤ 10⁶,图中可能有重边 |
| 子图定义 | 保留编号在 [ℓ, r] 内的点,以及两端都在区间内的边 |
| 距离约定 | 不连通时 d = 0;u = v 时 d = 0 |
| 统计口径 | 每张子图只累加 u < v 的点对 |
1 ≤ ℓ ≤ r ≤ n 的组合有 n(n+1)/2 张,n = 100 时是 5050 张O(n³) = 10⁶,乘上 5050 张正好是 10¹⁰,一秒连十分之一都跑不完G(ℓ, r) 比 G(ℓ, r−1) 只多一个结点 r。所以"新出现的更短路径"必然把 r 当作中间点,或者在 r 处出发/结束O(n²) 的松弛,单张子图就是 O(n²),总共 O(n⁴) ≈ 2.5 × 10⁷,一秒轻松跑完——这正是本题 n ≤ 100 的意义边:1–2 (w = 1)、2–3 (w = 2)。把 6 张子图逐张算一遍,看看 9 是怎么来的。
| (ℓ, r) | 子图里有谁 | 各点对距离(不连通记 0) | 小计 |
|---|---|---|---|
| (1, 1) | 只留点 1 | 没有 u < v 的点对 | 0 |
| (1, 2) | 点 1、2,边 1–2 | d(1,2) = 1 | 1 |
| (1, 3) | 点 1、2、3,两条边 | d(1,2) = 1,d(1,3) = 3,d(2,3) = 2 | 6 |
| (2, 2) | 只留点 2 | 没有点对 | 0 |
| (2, 3) | 点 2、3,边 2–3 | d(2,3) = 2 | 2 |
| (3, 3) | 只留点 3 | 没有点对 | 0 |
1 到 3 只能走 1 → 2 → 3
长度 1 + 2 = 3
(没有直连边,更没有别的绕法)
✅ 3
0 + 1 + 6 + 0 + 2 + 0
= 9
✅ 与样例输出一致
(2, 3) 在 G(1, 3) 里距离是 2,在 G(2, 3) 里距离也是 2,但它们属于不同的子图,要分别统计——求和式里的外层两个 Σ 就是在遍历所有子图。(u, v) 与 (v, u) 是同一个距离,所以内层写成 v = u … r,避免重复计数。边为 1–2 (100)、2–3 (100)、3–4 (100)、1–3 (10)、2–4 (10)、1–4 (1)。这张图每加一个点,都会出现新的"抄近路",正好检验增量思想。
| (ℓ, r) | 点对距离 | 小计 |
|---|---|---|
| (1, 1) | — | 0 |
| (1, 2) | d(1,2) = 100 | 100 |
| (1, 3) | d(1,2) = 100,d(1,3) = 10,d(2,3) = 100 | 210 |
| (1, 4) | d(1,2) = 11,d(1,3) = 10,d(1,4) = 1,d(2,3) = 21,d(2,4) = 10,d(3,4) = 11 | 64 |
| (2, 2) | — | 0 |
| (2, 3) | d(2,3) = 100 | 100 |
| (2, 4) | d(2,3) = 100,d(2,4) = 10,d(3,4) = 100 | 210 |
| (3, 3) | — | 0 |
| (3, 4) | d(3,4) = 100 | 100 |
| (4, 4) | — | 0 |
G(1, 2) 只有边 1–2,所以 d(1,2) = 100
加入点 3 后,边 1–3 (10) 可用
d(1,3) = 10;而 d(2,3) 只能绕 2 → 1 → 3 = 100 + 10 = 110 吗?
别忘了还有原边 2–3 (100),所以 d(2,3) = 100
小计 100 + 10 + 100 = 210
✅ 210
加入点 4 后新边:2–4 (10)、1–4 (1)
d(1,4) = 1(直连最短)
d(1,2):min(100, 1 + 10) = 11
d(3,4):min(100, 3 → 1 → 4 = 10 + 1) = 11
d(2,3):min(100, 2 → 4 → 3 = 10 + 100, 2 → 4 → 1 → 3 = 10 + 1 + 10) = 21
d(2,4) = 10
小计 11 + 10 + 1 + 21 + 10 + 11 = 64
✅ 64
0 + 100 + 210 + 64 + 0 + 100 + 210 + 0 + 100 + 0
= 784
✅ 与样例输出一致
G(1, 4) 里,d(2, 3) 的最短路是 2 → 4 → 1 → 3,同时用到了"更大的编号 4"和"更小的编号 1"。固定左端点 ℓ,把矩阵限制在 [ℓ, n] 跑 Floyd;中间点 k 每前进一步,就把子图 [ℓ, k] 的点对距离累加进答案
d[i][k] 这些"和 k 有关的距离"继续松弛。对每一对 (ℓ, r) 重新抠出子图,跑一次全源最短路
n(n+1)/2 张,每张都要 O(n³),| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 固定 ℓ + 增量 Floyd | O(n⁴) ≈ 2.5 × 10⁷ | 约 40 行 ✅ 推荐 |
| 逐张子图重建 + Floyd | O(n⁵) ≈ 10¹⁰ | 约 35 行 ❌ 超时 |
| 每个点各跑一次 Dijkstra | O(n · n² log n) 单张,整体 O(n⁶) | 约 60 行 ❌ 更慢 |
第一行输入 n m,随后 m 行输入 u v w(允许重边)。程序会按"固定 ℓ、r 递增"的顺序逐张子图累加点对距离,并列出每张子图的小计与累计答案。为便于观察,演示规模限制 n ≤ 6。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = (ll)1e15; // 最短路最大约 99 × 10⁶,1e15 足够当无穷大 const ll MOD = 1000000000LL; int n, m; ll g[105][105]; // 原图邻接矩阵(重边只留最小) ll d[105][105]; // 当前 Floyd 的工作矩阵 int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = (i == j ? 0 : INF); for (int i = 0; i < m; i++) { int u, v; ll w; scanf("%d %d %lld", &u, &v, &w); if (w < g[u][v]) { g[u][v] = w; g[v][u] = w; } // 重边取最小 } ll ans = 0; for (int l = 1; l <= n; l++) { // 1) 把 G(l, l) 的矩阵搬进来,之后让它"慢慢长大" for (int i = l; i <= n; i++) for (int j = l; j <= n; j++) d[i][j] = g[i][j]; for (int k = l; k <= n; k++) { // 2) 用刚加入的结点 k 作中间点松弛(范围留在 [l, n],供后续继续用) for (int i = l; i <= n; i++) { if (d[i][k] >= INF) continue; ll dik = d[i][k]; for (int j = l; j <= n; j++) if (dik + d[k][j] < d[i][j]) d[i][j] = dik + d[k][j]; } // 3) 此刻 d 在 [l, k] 上就是 G(l, k) 的全源最短路,累加 u < v for (int u = l; u <= k; u++) for (int v = u + 1; v <= k; v++) if (d[u][v] < INF) ans = (ans + d[u][v]) % MOD; } } printf("%lld\n", ans % MOD); return 0; }
[ℓ, n] 而不是 [ℓ, k],这样后面加入的点才能继承到正确的中间结果;③ 距离不要取模,只在累加进答案时取模——取模后的距离会破坏 min 的比较。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
if (w < g[u][v]) { g[u][v] = w; g[v][u] = w; } | 重边取最小 | 题目说可能有重边,只留最短那条对最短路才有意义 |
d[i][j] = g[i][j];(范围 [l, n]) | 初始化子图 | 每个 ℓ 都从"只有直连边"的状态重新出发 |
if (d[i][k] >= INF) continue; | 剪掉不可达 | 否则 INF + 边权 参与比较毫无意义,还容易溢出 |
for (int u = l; u <= k; u++) for (int v = u + 1; …) | 累加点对 | 只统计 u < v,避免同一距离被加两次 |
if (d[u][v] < INF) | 不连通记 0 | 不可达的距离按题意算 0,直接跳过即可 |
ans = (ans + d[u][v]) % MOD; | 边算边取模 | 答案可能极大,累加时就取模才不会溢出 |
[ℓ, k]——当下没错,但后面加入更大的点时 d[i][k] 已经过时,答案会偏大;② 忘了重边取最小,用"最后读到的边"覆盖,遇到重边就错;③ 把 INF 也累加进答案,那种"不连通"的点对必须当 0 跳过;④ 对距离提前取模,min 的比较被破坏,结果完全不可信。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 2 | 9 | 题面样例 1:链式子图,逐张累加得 9 |
4 6 | 784 | 题面样例 2:点 4 加入后老点对也会被改短 |
2 2 | 3 | 重边:两点的子图里只认最短那条 3 |
4 2 | 6 | 子图可能不连通:不连通点对一律记 0 |
2 2 | 1000000 | 边权取到上限 10⁶,验证不会溢出 |
5 4 | 56 | 最长链:所有点对距离都要算,考察累加次数 |
100 4950 完全图(边权随机) | 运行验证 | 最大规模,考察 O(n⁴) 是否跑得动 |
[ℓ, n] 吗?③ 只累加 u < v 吗?④ 不连通的距离跳过了吗?[ℓ, k]:样例 2 就会挂——G(1, 4) 里 d(2, 3) 要用到点 4 与点 1 的中间结果。min 一下。min 的比较依赖真实大小,取模后答案必错。(n − ℓ + 1)² 的松弛(n − ℓ + 1)³,合计 Σ (n − ℓ)³ ≈ n⁴ / 4Σ (k − ℓ)² / 2 ≈ n⁴ / 24只需要两张 101 × 101 的矩阵:g 保存原图(重边取最小),d 作为 Floyd 的工作矩阵。答案用 long long 边算边取模,不需要存任何中间结果。
✅ 2.5 × 10⁷ 量级在 C++ 里不到 0.1 秒,关键就是把 O(n⁵) 的"逐张重建"砍成 O(n⁴) 的"增量松弛"。
// 「固定一端 + 增量 Floyd」通用套路 // 场景:要对所有区间 [l, r] 的诱导子图做全源最短路 for (int l = 1; l <= n; l++) { // (1) 只把 [l, n] 的直连边放进矩阵 for (int i = l; i <= n; i++) for (int j = l; j <= n; j++) d[i][j] = g[i][j]; for (int r = l; r <= n; r++) { // (2) 用"新来的点 r"当中间点,在 [l, n] 上补一次松弛 // 范围一定留到 n:后面还要用它去松弛更大的点 for (int i = l; i <= n; i++) { if (d[i][r] >= INF) continue; for (int j = l; j <= n; j++) d[i][j] = min(d[i][j], d[i][r] + d[r][j]); } // (3) 此时 d 在 [l, r] 上就是 G(l, r) 的全源最短路 // 需要统计什么就顺手统计什么 } } // 复杂度:Σ_l (n − l)³ ≈ n⁴ / 4,而不是"逐张重建"的 n⁵ // 判断能否用增量:相邻两个状态是否只差"一个点 / 一条边 / 一个字符"
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 固定一端枚举 | 把二维的 (ℓ, r) 变成"一维长大",中间点 k 复用 | 所有"区间子图"类统计题 |
| 增量松弛 | 新点只多一层中间点,老结果不丢 | 动态加点(在线)最短路、Floyd 的在线版本 |
| 重边取最小 | 用邻接矩阵天然合并重复边 | 所有用矩阵存图的最短路题 |
| 不计不连通 | "不连通记 0"= 直接跳过该点对 | 贡献统计类问题里的"不可达特判" |
G(ℓ, r) 里仍保留跨出区间的边),增量法还能用吗?(提示:不行——那时 G(ℓ, r) 会通过区间外的点相连,"只差一个点"的性质消失了。增量法的前提是"局部性":新状态必须只比旧状态多一点点信息。)