第一次看到 Sightseeing trip 这个题名我心想又是哪个旅行推销员的变种等把题面读完才反应过来原来它要的是无向图最小环。给定一张带权无向图找一个包含至少三个点的简单环让环上边权总和最小并输出环上各点。这是一道体现 Floyd 本质的经典题也是我在 OJ 上被教育得最狠的一题——因为它的解法不是“多源最短路”那么表面而是把 Floyd 每一轮“允许经过的中间点集合”这个语义拆开来用。对刚学完 Floyd 只想套板子的选手来说这是个极好的思维升级样本趁着这几天又翻出来做了一遍我把这次想明白的细节完整写下来。1. 题目到底在问什么先把最小环问题看穿1.1 题面与输入输出特征题目给一张带权无向图点从 1 到 n 编号边若干条。要求找出一个环满足三点环上至少有 3 个点也就是不能出现 1→2→1 这种来回两条边的“二元环”环上的点是简单环不能重复环上所有边权之和最小并且需要输出环上的顶点序列。输出很有意思不是只输出权值而是把路径顶点打出来。这意味着你不光要算出最小环长度还得把一条具体路径还原出来。题面里说了如果有多个答案输出任意一个即可。数据范围对算法选择的指向性非常明显n 在 100 这个量级。100 是什么概念O(n^3) 10^6 级别的运算随便跑但你要是想暴力枚举环上的点再逐条验证n 一旦到 100组合数立刻爆炸根本不可行。所以看到 n ≤ 100配合“最短路”“环”“路径输出”这些关键词第一反应就该是 Floyd 框架下的动态规划。但这里要强调一点Floyd 最小环绝对不等于“把全源最短路跑完再随便拼一拼”。如果你只把 Floyd 当成一个求 dist 的黑盒这道题你还是做不出来因为它的核心不在于最终的最短路表而在于 Floyd 中间某几次迭代时那份“还没算完”的距离矩阵。1.2 为什么直接暴力会翻车先说最简单、也最容易想到的暴力思路枚举三个点 i、j、k检查它们两两之间是否有边如果三条边都存在就构成一个三角形环把三条边权和算出来更新答案。这个思路有一个致命的盲点它只能找到长度为 3 的环。题目完全可能出现一个四边形、五边形甚至更大环它们的总权值比任何三角形都小。举个例子一个四边形环 1-2-3-4-1每一条边权都很小但任意三点之间不一定存在彼此相连的边。枚举三角形根本抓不到这种答案。再想一个思路枚举环的起点DFS 沿着边走能走回起点就更新答案。理论上没问题但最坏情况下环的数量是指数级的DFS 会在一张稠密图里反复横跳剪枝剪到手软。n100 的朴素 DFS 大概率超时而且你还要处理路径记录、去重、避免重复枚举同一个环实现复杂度比想象中高得多。还有同学会想到“先跑一遍全源最短路再枚举边 u-v用 dist[u][v] g[v][u] 去找环”。这个思路看似聪明但有两个硬伤第一如果 u 和 v 之间恰好有直接边dist[u][v] 很可能就是这条直接边的权值再加一条返回边拼出来的就是二元环不是合法答案第二你很难判断这条最短路和补上的边是否真的构成简单环即使强行判断也要在边界条件上打一堆补丁。标准解法干脆从一开始就不走这条弯路而是用一种更结构化的方式拆环。1.3 一个关键视角每个环都有个“最大编号锚点”任何一张图里给定任意一个简单环把环上所有点按编号排一排一定有一个编号最大的点。假设这个点叫 k。现在把 k 从环上摘掉剩下一条从某个点 i 到另一个点 j 的简单路径而且 i、j 的编号都比 k 小。这件事本身平淡无奇但它给了我们一个非常重要的拆分方式一个环 一条 i 到 j 的路径 边 (j, k) 边 (k, i)。注意这里的关键点路径 i→j 上的所有中间节点因为整个环是简单环所以它们既不会是 i、也不会是 j、更不会是 k。而环上的最大编号既然已经是 k说明路径 i→j 经过的所有中间点编号也都小于 k。于是问题就转化了如果我们能快速知道在“只允许经过编号小于 k 的点作为中间点”的限制下i 到 j 的最短路是多少那么再补上两条直接边就能拼出一个完整环。这就是 Floyd 算法每一轮迭代做到一半时的 dist 矩阵天然携带的信息。2. Floyd 的最小环套路先别急着更新最短路2.1 重新认识 Floyd 的 dist很多人学 Floyd 时只背了那个三重循环却忽略了它背后的含义。标准的 Floyd 状态可以写成dp[k][i][j] 表示从 i 到 j只允许经过编号不超过 k 的点作为中间点能得到的最短路长度。初始时 k0也就是不允许经过任何中间点dp[0][i][j] 就是原图的直接边权没有边就用无穷大表示。每一轮用 k 号点作为“中介”尝试刷新所有 i、j 对就完成了一次状态转移。滚动数组压掉第一维之后代码长成我们熟悉的样子for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (dist[i][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j];这里的循环顺序可不是随便写的。外层 k 从 1 到 n每走一轮dist[i][j] 的语义就扩大一次“允许的中间点集合”。等到 k 循环全部结束dist[i][j] 才是真正的全源最短路。但在第 k 轮刚开始、还没执行更新的时候dist[i][j] 的语义是“只允许经过编号小于 k 的点作为中间点的最短路”。这个“第 k 轮之前的 dist”就是整道题的钥匙。如果只把 Floyd 当作一个黑盒等到全部求完再查答案那就正好错过了它最有价值的部分。2.2 第 k 轮之前的 dist是查环的“半成品”就像 1.3 节说的把环上的最大编号点 k 摘掉剩下的路径 i→j 中间点编号全小于 k。而在第 k 轮还没开始更新的时候dist[i][j] 恰好满足这个约束。所以我们可以做这样的检查ans min(ans, dist[i][j] g[i][k] g[k][j])其中 g[i][k] 和 g[k][j] 是原图上的直接边权i、j 都限制在小于 k 的范围里并且 i ≠ j。为什么每个环都能被这个式子抓到因为任取一个简单环它的最大编号点就是唯一的那个 k。把 k 摘掉后其余点里面与 k 相邻的那两个点就是 i 和 j。dist[i][j] 计算出的最短路径加上 (j,k) 和 (k,i) 两条边必然闭合成一个环。不同环最大编号点不同枚举 k 时天然不会重复统计同一个环。这就是“每个环都有唯一锚点”的威力通过限制最大编号顶点既保证了环至少有三点个又避免了重复枚举。相反如果你不限制编号枚举 i、j、k 就会把同一个环的正反方向、不同起点计算很多次还得额外去重。2.3 先查环再更新顺序不能反这一节的标题应该加粗先查环再更新顺序不能反。原因很简单。如果在第 k 轮先把 all-pairs 最短路更新完再回头检查 dist[i][j] g[i][k] g[k][j]此时 dist[i][j] 可能已经经过了 k 号点。那拼出来的东西还叫环吗k 号点既能作为路径中间点出现一次又作为两条直接边的端点出现路径里可能已经包含了边 (i,k) 或者 (k,j)拼完之后要么退化成一条边要么形成重复点的“伪环”。正确的代码骨架应该是for (int k 1; k n; k) { // 第一步用第 k 轮之前的 dist检查以 k 为最大编号顶点的环 for (int i 1; i k; i) for (int j i 1; j k; j) if (dist[i][j] g[i][k] g[k][j] ans) ans ...; // 第二步再执行标准 Floyd 更新允许 k 作为中间点 for (int i 1; i n; i) for (int j 1; j n; j) if (dist[i][j] dist[i][k] dist[k][j]) dist[i][j] dist[i][k] dist[k][j]; }这两步的顺序就是整道题的生命线。整个算法复杂度 O(n^3)对 n100 来说就是 100 万次循环毫无压力。这个套路也不止能过这一题后面遇到很多“环 最短路”的组合题都可以用同样的思想迁移。3. 把最小环路径捞出来pre 数组与回溯3.1 pre[i][j] 到底存什么光算长度不够题目要求输出顶点序列。这时候我们需要在 Floyd 更新最短路的路上额外记录一条路径信息。常见的做法是用 pre[i][j] 表示在当前记录的最短路 i→...→j 中j 的前驱是哪一个点。注意是 j 的前驱不是 i 到 j 路径的第一个中转点也不是简简单单把 i 记下来。如果你记的是“第一个中转点”后续回溯会非常别扭。初始时如果 i 和 j 之间有一条直接边那当前这条“最短路”就是 i→jj 的前驱自然是 i所以 pre[i][j] i。没有直接边就置 0代表路径不存在。Floyd 更新的时候如果发现 dist[i][j] dist[i][k] dist[k][j]说明新的更短路径要绕过 ki → ... → k → ... → j。这时候 j 的前驱应该是什么不是 k而是 k 到 j 这条最短路径上 j 的前驱也就是 pre[k][j]。所以更新式是dist[i][j] dist[i][k] dist[k][j]; pre[i][j] pre[k][j];这个细节非常容易写错。我第一次就写成了 pre[i][j] k结果输出路径时直接跳点路径变成了“i k j”这种不连续的三段检查了半天才意识到k 只是路径里的一个中间点k 后面可能还跟着别的节点比如 k→a→j那么 j 的前驱应该是 a而不是 k。3.2 回溯代码与实例有了 pre 数组还原路径就很简单。写一个递归函数把 i 到 j 路径上的中间点依次找出来void get_path(int i, int j) { if (pre[i][j] i) return; // i 直接到 j没有中间点 get_path(i, pre[i][j]); // 先处理 i 到前驱的部分 path.push_back(pre[i][j]); // 再把当前前驱加进去 }我们用一个图示例走一遍假设最短路是 1→2→3→4那么 pre[1][4] 3pre[1][3] 2pre[1][2] 1。调用 get_path(1,4)pre[1][4] 3不等于 1递归 get_path(1,3)pre[1][3] 2递归 get_path(1,2)pre[1][2] 1等于 i返回不做事回到上一层push pre[1][3] 2回到最外层push pre[1][4] 3。最后 push 4 或者由调用者 push路径 1 2 3 4 就拼出来了。3.3 拼环顺序与输出细节找到候选环时我们手头有三样东西i、j、k以及 i 到 j 的最短路。拼环的顺序是先把 i 放进去然后调用 get_path(i,j) 把 i 到 j 路径上的所有中间点放进去再放 j最后放 k。这样得到的顶点序列是i, (i到j的中间点), j, k它表达的环是i → ... → j → k → i。因为原图是无向图g[i][k] 和 g[k][j] 都等价于对应方向的边所以闭合关系完全成立。这道题允许多个解输出任意一个所以起点从 i 开始完全没问题。有一点要再提醒get_path 里 pre 数组记录的是“当前 dist 对应的那条最短路”。如果在 Floyd 更新时遇到等权路径不去更新 pre那么记录的就是先发现的那条最短路。对于最小环来说等权不管选哪条环总权值都一样对答案没有影响。题目只要求输出一个合法答案不需要字典序最小。4. 可以直接抄的完整代码4.1 代码#include cstdio #include cstring #include vector #include algorithm using namespace std; const int N 105; const int INF 0x3f3f3f3f; int n, m; int g[N][N], dist[N][N]; int pre[N][N]; vectorint path; void get_path(int i, int j) { if (pre[i][j] i) return; get_path(i, pre[i][j]); path.push_back(pre[i][j]); } int main() { while (scanf(%d%d, n, m) 2) { memset(g, 0x3f, sizeof(g)); memset(pre, 0, sizeof(pre)); for (int i 1; i n; i) g[i][i] 0; for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); if (u v) continue; // 自环直接忽略 if (w g[u][v]) { // 重边只保留最小权值 g[u][v] g[v][u] w; pre[u][v] u; pre[v][u] v; } } memcpy(dist, g, sizeof(g)); long long ans 1LL 60; path.clear(); for (int k 1; k n; k) { // 先查环第 k 轮之前的 dist中间点编号全部小于 k for (int i 1; i k; i) { for (int j i 1; j k; j) { if (dist[i][j] INF) continue; if (g[i][k] INF || g[k][j] INF) continue; long long cur 1LL * dist[i][j] g[i][k] g[k][j]; if (cur ans) { ans cur; path.clear(); path.push_back(i); get_path(i, j); path.push_back(j); path.push_back(k); } } } // 再更新最短路允许 k 作为中间点 for (int i 1; i n; i) { for (int j 1; j n; j) { if (dist[i][k] INF || dist[k][j] INF) continue; if (dist[i][j] dist[i][k] dist[k][j]) { dist[i][j] dist[i][k] dist[k][j]; pre[i][j] pre[k][j]; } } } } if (ans 1LL 60) { printf(No solution.\n); } else { for (int i 0; i (int)path.size(); i) { if (i) printf( ); printf(%d, path[i]); } printf(\n); } } return 0; }4.2 关键行解读这段代码里有一个非常值得学习的细节INF 没有用 2147483647而是用了 0x3f3f3f3f。为什么因为 0x3f3f3f3f 大约是 10.6 亿两个 INF 相加约 21.2 亿还没有超过 int 上限 21.4 亿所以标准 Floyd 更新里 dist[i][k] dist[k][j] 不容易因为溢出变成负数。如果 INF 直接设成 0x7fffffff两个 INF 一加就溢出成负数dist 矩阵直接爆掉Floyd 会算出各种离谱的“负权路径”。查环时计算dist[i][j] g[i][k] g[k][j]是三个数相加最坏情况约 31.8 亿已经超过 int 上限所以代码里用1LL * dist[i][j] ...转成 long long 再比较。虽然我们在更新前已经判断了三个值都不是 INF但加上 long long 转换属于防御性编程成本为零为什么不加呢。重边处理也很重要。两个点之间输入多条边时只保留权值最小的那条并且同步更新 pre。如果等权重边可以不更新 pre因为走哪条都一样。自环直接 continue 忽略。自环在这个问题里没有任何意义——题目要的环至少三个点自环只会在 dist[i][i] 上引入一个正权值不影响任何 ijk 的枚举忽略它反而让代码更干净。4.3 关于这份代码的正确性说明这份代码和常规题解版本的思路完全一致针对 n100 的数据跑一遍耗时基本可以忽略。多组输入时数组和 path 都在 while 循环里重新初始化不会出现上一组数据的残留。如果你用的是老式 C 编译器这份代码也完全兼容没有用到任何高版本特性。路径输出时每个数字后面用空格分隔末尾换行无解时输出No solution.别漏了那个句号题目就是这样的格式要求。5. 常见错误与自测用例5.1 新手最容易踩的四个坑我刷这道题的时候以及后来帮别人 debug 的时候翻来覆去就那几种错误。错误表现根本原因解决办法输出一堆重复点甚至输出负数先做完整 Floyd 更新再回头查环调换顺序先查环再更新路径输出跳点比如 1 3 4 这种中间少点pre 更新写成 pre[i][j] k改成 pre[i][j] pre[k][j]小数据能过稍微大点数据答案变成超大负数INF 设成 0x7fffffff加法溢出INF 用 0x3f3f3f3f并用 long long 计算 cur一直输出 No solution明明有环重边没处理两点间较大边权覆盖了较小的边权或者自环污染了 dist读边时取 min自环 continue这四个坑基本覆盖了 90% 的“我明明照着思路写为什么不对”。尤其是第一个查环和更新顺序写反属于这类题最经典的翻车现场。我建议你把循环顺序当成公式一样记牢先查环再更新。5.2 三组自测数据写完代码一定要自己造数据测不能只依赖题目样例。下面三组很简单但能覆盖核心逻辑。第一组三角形3 3 1 2 1 2 3 1 3 1 1最小环就是三角形长度 3。程序应该输出类似1 2 3的序列。第二组无解情况3 2 1 2 1 2 3 1图只是一条链根本闭合不成环输出No solution.第三组四边形带重边4 4 1 2 5 2 3 3 3 4 4 4 1 2这个图只有一个四边形环 1-2-3-4-1总权值 534214。程序输出1 2 3 4方向也可能相反但都是合法环。有兴趣的话还可以加一组3 4 1 2 10 1 2 1 2 3 1 1 3 100这里 1 和 2 之间有重边必须选权值 1 的那条三角形环 1-2-3-1 的总权值是 11100102。如果读边时直接赋值不取 min把 10 覆盖成 1 或者反过来处理不当答案就会错。5.3 复盘我自己写挂的两个地方第一个坑就是循环顺序。我当时是用“跑完整 Floyd 再枚举 k”的惯性思路写的样例第一发直接输出一串乱七八糟的点。为什么因为跑完的 dist 已经把所有点都放开作为中间点了dist[i][j] 很有可能经过 k再补两条边k 被算了两次路径里出现“环套环”根本不是合法解。后来把查环挪到 Floyd 更新之前样例瞬间通过那种“原来是这里”的感觉我现在还记得。第二个坑是 pre 数组。一开始图省事更新时直接写 pre[i][j] k结果输出路径时总觉得少了几个点。后来我手动模拟了一条经过三个中间点的路径才发现 pre[k][j] 才是正确的。这个错误隐蔽就隐蔽在数据小、路径短的时候pre[i][j] k 和 pre[k][j] k 结果经常一样一旦路径变长立刻露馅。所以做这类题即使样例能过也一定要造一条长路径自己模拟一遍。6. 从这题延伸出去最小环还能怎么考6.1 有向图怎么改上面所有代码都建立在无向图的基础上循环里用 ij 去重g[i][k] 和 g[k][j] 两侧对称。如果题目换成有向图改动也不大首先不能再写 ij 了要枚举所有 i、j 都小于 k 且 i ≠ j 的二元组其次拼环的方向必须严格吻合公式要改成dist[i][j] g[j][k] g[k][i]因为环是 i → ... → j → k → i所以补的两条边要保证方向j→k 和 k→i。无向图里因为边对称写成 g[i][k] g[k][j] 也没问题有向图里写错方向答案就是错的。很多从无向图改有向图的题解第一步就死在这两条边的方向上。有向图最小环一样可以用“最大编号锚点”枚举每个有向简单环也必然存在唯一的编号最大点。整体思路保持完全不变只是边界条件和边的方向需要细抠。6.2 无权图与计数问题如果题目改成无权无向图求最小环包含几个点我们甚至不需要边权数组把每条边权值看作 1跑同样的算法最后 ans 就是最小环的边数。因为所有边权都是 1路径长度就等于经过的边数最小环权值就是最小环长度。实现上只需要把读边的 w 固定为 1其余代码一字不改。有些变种题会问“有多少个不同的最小环”。这就要在 Floyd 更新最短路的阶段同步维护“最短路条数”在查环阶段也要想办法去重。简单环的计数比单纯求值复杂得多因为同一个环可能被多个最大编号点枚举到去重通常要约定一种规范表示比如把环的顶点序列最小表示作为唯一键。这个方向要是深挖下去又是一篇文章的体量这里先点到为止。6.3 负权边与负环的边界最小环问题在竞赛里默认边权为正这个假设很关键。Floyd 能处理负权边前提是图中没有负环但最小环问题一旦允许负权边整个问题的定义都要重新推敲如果图里存在负环最小环的权值就是负无穷算法中“简单环”的约束会失效Floyd 在负环图上更新 dist 会不断变小循环输出也会出问题。所以看到最小环题先确认边权范围。如果题目没有明确说正权大概率也是“保证无负环且答案有限”的友善设定但写代码时多加两个判断总是好的。我后来做环相关题目第一反应都会先在草稿纸上画一个环把最大编号的那个锚点标出来再看剩下那段路径能不能用某个 dist 或者 dp 状态表达。“锚点拆环”这个思路适用范围很广不仅限于 Floyd 最小环。比如有些状态压缩 DP 求最短哈密顿回路也是先固定起点再枚举路径闭合本质都是在找一个切入点把环拆成好处理的一段路径和一条闭合边。这道 Sightseeing trip 虽然只是入门题但它教你的这种拆环方式会在后面很多题里反复出现每次遇到都值得感谢当年那个把自己写挂的下午。