第一部分 题目分析1、看懂题目1有一张无向带权图。例如1 --2-- 2 --3-- 3 --4-- 4 \ | 5 1 \ | 52图中一共有n 个点 m 条边3现在不是只求一次最短路。而是要求对于所有区间[l,r]都建立一个子图。4例如l2 r5那么保留2 3 4 5其它点全部删掉。5然后要求这个子图里面所有点对最短路之和。6最后所有区间全部加起来。2、举个例子1假设1 2 3三点。2边1-21 2-323那么区间有[1,1] [1,2] [1,3] [2,2] [2,3] [3,3]4每一个区间都要求所有点之间最短路是不是非常多5如果暴力O(n²) 每次跑 Floyd O(n³) 总复杂度 O(n⁵)显然不可能。需要更高效的做法。第二部分 数据范围告诉我们什么1、题目里最关键的是n≤100为什么100 非常小。说明可以允许100³甚至100⁴但是100⁵就炸了。2、所以我们要努力做到O(n⁴)第三部分 最容易想到的方法1、每个区间跑一次 Floyd区间数量n²每次n³总共n⁵2、这是第一种思路。直接淘汰。第四部分 Floyd到底干了什么1、有的同学不会观察 Floyd。它实际上就是一个一个加入中转点。2、例如开始没有中转点然后加入1再加入2再加入3……3、经典代码for(k) for(i) for(j) distmin(...)其实就是当前允许经过1~k这些点。4、所以Floyd最大的特点它是动态增加中转点。这就是本题突破口。第五部分 本题也是不断增加点1、观察区间。1固定左端点l32那么[3,3] ↓ [3,4] ↓ [3,5] ↓ [3,6]是不是每次只增加一个点3增加的是r例如[3,5] ↓ [3,6]只增加64是不是跟Floyd加入中转点特别像第六部分 如何利用1、对于固定l先复制一份最初距离gf;2、为什么因为f 永远保存原图。而g 不断更新。所以每换一个l重新开始。3、随后rl rl1 rl2一直扩大。每扩大一次新增一个点 r那么只需要让 r 做一次 Floyd 中转点即可。4、代码就是for(i) for(j) g[i][j] min( g[i][j], g[i][r]g[r][j] );是不是跟 Floyd 一模一样5、区别只是普通 Floydk1 2 3 ... n这里kr每次只增加一个。第七部分 为什么这样就是对子图1、例如l41第一次r4允许中转42第二次r5允许4 53第三次r6允许4 5 62、是不是永远都是[l,r]里面的点3、没错。所以求出来就是子图 [l,r] 最短路第八部分 为什么不用前面的点1、因为1 2 3已经删掉了。它们不存在。自然不能作为中转点。2、所以只加入r即可。第九部分 为什么复制 gf1、看看参考代码for(i) for(j) g[i][j]f[i][j];为什么2、假设l1更新结束以后g 已经包含很多信息。下一次l2如果继续用g里面还有点1 参与过中转。那就错了。2、所以必须重新复制。第十部分 为什么只统计 i~r1、代码for(il;ir;i) for(ji;jr;j)为什么2、因为题目只要求区间里面。而不是整个图。3、另外由于dist(i,j) dist(j,i)无向图。4、所以统计i≤j即可。避免重复。第十一部分 参考程序#include cstdio #include algorithm using namespace std; const int N 105; const int mod 1e9; int n, m; int f[N][N]; int g[N][N]; int ans; int main() { scanf(%d%d, n, m); for (int i 1; i n; i) { for (int j 1; j n; j) f[i][j] mod; f[i][i] 0; } for (int i 1; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); f[u][v] min(f[u][v], w); f[v][u] min(f[v][u], w); } for (int l 1; l n; l) { for (int i 1; i n; i) for (int j 1; j n; j) g[i][j] f[i][j]; for (int r l; r n; r) { for (int i 1; i n; i) for (int j 1; j n; j) g[i][j] min(g[i][j], g[i][r] g[r][j]); for (int i l; i r; i) for (int j i; j r; j) ans (ans g[i][j]) % mod; } } printf(%d\n, ans); return 0; }1、初始化f[i][j]INF; f[i][i]0;表示没有边 无限大 自己到自己 02、然后读边f[u][v]min(...) f[v][u]min(...)为什么min因为有重边。保留最短。3、接着for(l1;ln;l)固定左端点。复制gf;然后for(rl;rn;r)不断扩大区间。新增一个点r于是for(i) for(j) g[i][j] min( g[i][j], g[i][r]g[r][j] );4、最后for(il;ir;i) for(ji;jr;j) ansg[i][j];统计答案。5、整个算法时间复杂度外层 l O(n) × r O(n) × Floyd一次更新 O(n²) O(n⁴)当 (n100) 时大约是 (10^8) 级别操作在题目的限制下是可以接受的。第十二部分 本题考察什么1、这题真正考察的不是 Floyd 模板而是能否发现 Floyd 的本质是“逐步加入中转点”再把这种思想迁移到区间子图中。2、很多同学都会背for(k) for(i) for(j)3、真正优秀的同学会想到加入一个点就做一次松弛区间右端点每次增加一个点正好可以作为新的中转点固定左端点、逐步扩大右端点就能把总复杂度从O(n⁵)优化到O(n⁴)。本节课总结这一题最值得记住的不是代码而是下面四句话✅① Floyd 的核心不是三层循环而是“不断加入新的中转点”。✅② 固定左端点右端点每次增加一个点就相当于新增一个中转点。✅③ 每增加一个点只需要执行一次 Floyd 的松弛更新而不用重新计算全部最短路。✅④ 学算法不要只记模板要理解算法背后的思想才能在新题目中灵活迁移。