POJ 1734 最小环求解：Floyd算法原理与路径回溯实现详解

做图论专题绕不开 POJ 1734 这道 Sightseeing trip。我一开始以为它就是个普通最短路模板题读完题才发现要的是“最小环”——在一个无向带权图里找权值最小的闭合回路而且必须把环上经过的景点编号按顺序打印出来。题目本身不难但 Floyd 求最小环这个思路以及路径输出的实现还是有不少容易翻车的细节。这篇文章就按我自己的调试过程把整条线捋一遍从题目建模到原理、再到可 AC 的完整代码适合第一次接触最小环的选手也适合想彻底搞懂 Floyd 路径回溯的读者。1. 从“观光旅游”到最小环题目到底在问什么1.1 把景点和道路抽象成一张无向带权图题面说的是一个人想开车逛若干个景点每个景点之间有道路连接每条路都有长度。他希望找一条闭合的游览路线从某个景点出发沿着道路走一圈最后回到出发点。这个“一圈”在图上就是一个环。所以说到底我们要解决的是给定一张无向图点数是景点数边是道路边权是道路长度找一条经过至少 3 个不同景点的闭合回路使得回路上的边权和最小如果不存在这样的环输出No solution.。这里的“至少 3 个不同景点”很关键。两个景点之间如果有多条路拿两条不同的路来回走也能构成一个 2 元环但题目明确不认这种。所以最小环的候选环至少是三角形也就是环上节点数不小于 3。提示在读题时要注意边权是正的。负权边会导致 Floyd 检测负环最小环问题就失去意义了。1.2 “最短路原路返回”不是环别被直觉带偏新手最容易犯的错误是想当然地把问题简化成随便选一个起点跑到最远点再沿最短路回来这不就是一个闭合回路吗错。最短路原路返回相当于把同一条边走了两遍路线重复且毫无观光意义这不是环。图论里的“环”要求路径上的点互不重复除了起点和终点重合。所以从朴素思维出发要枚举环上的所有排列组合这在节点数稍大时是灾难性的。n100 时暴力枚举所有可能的环排列复杂度是阶乘级别的完全不可行。正因为 n 只有 100我们可以用 O(n^3) 的 Floyd 算法在动态规划的过程中顺手把最小环找出来。用人话说这道题的核心不是“怎么走最短路”而是“怎么在所有闭合圈里挑权值最小的那个圈”。2. 先排除三种“看起来可行”的解法在讲正解之前我把自己最开始想过的几种方案都拿出来对比一下。不是浪费时间而是只有弄明白它们为什么不行才能理解 Floyd 求最小环为什么是这样一个结构。2.1 暴力 DFS 枚举环指数爆炸写起来还麻烦最容易想到的当然是 DFS从每个点出发沿着没走过的点继续走一旦回到起点就统计当前路径和。这个思路很朴素但复杂度是 O((n-1)!)。在 n100 的图里这个复杂度别说跑测试光是想象一下都头皮发麻。就算加剪枝也无法保证在极限数据下通过。而且暴力 DFS 还要解决“如何避免重复枚举同一个环”的问题一个环从不同起点、不同方向走会得到不同的节点序列去重又是一层麻烦。所以这个方案在正确性和性能上都是最差的。2.2 枚举每条边并“断开”后跑最短路可行但低效第二个思路是有一定可行性的对于一条边 (u, v)如果它属于某个最小环那么环的剩余部分就是从 u 到 v 的另一条路径且这条路径不经过边 (u, v)。所以我们可以枚举每条边临时把它从图中“删掉”然后跑一次 u 到 v 的最短路把最短路长度加上该边权值就是一个包含该边的环的长度。这个方法的复杂度是 O(m * 单次最短路)。在 n100、m 可能到几千的情况下用堆优化的 Dijkstra 跑 m 次最坏可能接近 O(n^4)虽然 n 小也许能过但实现起来非常啰嗦要处理重边、要在删边后恢复、还要留一份路径用于输出。而且这种思路隐含了一个 bug 风险——如果 u 到 v 的最短路恰好经过 (u, v) 的另一条平行边那需要额外处理重边问题。2.3 跑完 Floyd 再拼环三重“最短路”拼出来的可能不是环这个方案我猜很多人踩过坑先完整跑一遍 Floyd得到所有点对之间的最短路 dist然后枚举三个点 i、j、k用dist[i][j] dist[j][k] dist[k][i]更新答案。直觉上这很合理三段最短路首尾相接正好构成一个闭合回路。问题在于三段最短路可能共享节点。比如dist[i][j]的最短路已经经过了 k那么再把dist[j][k]接上k 会被走两次得到的“环”不是一个合法的简单环。而且这种重叠不一定能在数据上体现出来最终你可能得到一个数值偏小的伪答案路径回溯时还会打印出重复节点。完全跑完 Floyd 再拼环本质上是把三条只保证“两端点最短”的路径强行拼接它们之间没有任何互斥约束。所以 Floyd 求最小环的正确姿势必须利用 Floyd 的动态规划过程在每一轮松弛之前“截获”环而不是等全部跑完再拼。解法复杂度路径输出难度正确性风险暴力 DFSO((n-1)!)需要去重理论上正确实际不可行枚举边 最短路O(m * S)S 为单源最短路中要处理删边和重边重边处理麻烦跑完 Floyd 再拼环O(n^3)低三段路径可能重叠产生伪环Floyd 过程中找环O(n^3)低配合 path 数组正确且无重叠3. Floyd 增量松弛与最小环的相遇点3.1 “第 k 轮”这个时间窗口是解题钥匙Floyd 算法的核心是三重循环最外层枚举中间点 k。在进入第 k 轮松弛之前dist[i][j]的含义是严格的从 i 到 j只允许经过编号小于 k 的节点作为中间点得到的最短路径。这一点是整个最小环算法的地基。为什么这么说我们想象一个简单环假设它的节点编号最大是 K。在这个环上取与 K 相邻的两个节点 a 和 b那么环去掉 a-K 和 b-K 这两条边之后剩下的就是从 a 到 b 的一条路径而且这条路径上的所有节点编号都小于 K。所以当外层循环处理到 kK 时dist[a][b]已经能够表示这条路径的长度或者说dist[a][b]一定不大于环上 a 到 b 的这段路径。于是当外层循环执行到 k 时我们枚举所有 i、j只要 i、j 都小于 k且边 (i, k) 和 (k, j) 存在那么环的长度 dist[i][j] e[i][k] e[k][j]这里的思路是把 k 当作环上编号最大的那个点i 和 j 是 k 在环上的两个邻居dist[i][j]走的是环上剩下的那段路径。因为在这轮松弛之前dist[i][j]还不能经过 k所以这个组合天然避开了“路径中包含 k”的问题。用个生活化的类比Floyd 像盖楼第 k 轮之前只有 1 到 k-1 层之间的电梯路线是确定的第 k 层的电梯还没投入使用。此时如果发现从 i 到 j 可以走 1 到 k-1 层的内部电梯再通过第 k 层的两个门进入 k就形成了一个完整的圈。等到第 k 层电梯投入使用后再去找就会走出包含 k 的重复路线。3.2 为什么环节的另外两条边必须用原始边表 e 而不是 dist这个点是我写代码时最容易忽略的也是很多博客里没有讲透的。求环的公式里dist[i][j]用的是一路松弛下来的最短距离但e[i][k]和e[k][j]必须用原始图的直接边权不能写成dist[i][k]和dist[k][j]。原因有两个第一dist[i][k]可能已经经过了很多节点其中包括 j 或者 dist[i][j] 路径上的节点。这样dist[i][j] dist[i][k] dist[k][j]拼出来的就不是一个简单环而是路径的相互重叠。由于边权为正重叠路径虽然可能得到一个更小的“伪环”但这个伪环不能作为观光路线。第二从“最大编号点”的证明上看k 必须是环上与 i、j 直接相邻的那个点。如果 i 到 k 之间还隔着别的点那么这个环真正的最大编号点并不是当前轮次的 k。硬要用 dist 去连接 k就会破坏“每轮只负责以 k 为最大编号点的环”的划分导致同一个环被多次乱算。所以正确姿势是在一开始就维护一个e[][]原始边权矩阵重边取最小并在找环时把e[i][k]和e[k][j]当作环的“收口边”。如果它们之间没有直接边值就是 INF自然不会被选入答案。3.3 先查环再松弛顺序不能反Floyd 求最小环的模板中每一轮 k 的循环体是这样的用当前dist[][]找最小环用 k 去松弛更新dist[][]。顺序为什么重要因为一旦用 k 松弛了dist[i][j]dist[i][j]就可能包含 k 作为中间点。然后我们再回头用dist[i][j] e[i][k] e[k][j]来组环那么dist[i][j]这条路径内部已经偷偷走过 k 一次整个组合就会把 k 绕进去两次不再是简单环。另外从“最大编号点”的划分角度讲第 k 轮开始前的dist[i][j]只允许经过编号小于 k 的节点这正是我们希望保证“环上除 k 以外所有节点都小于 k”的前提。一旦先松弛这个前提就被破坏了。所以“先找环、后松弛”不是代码风格问题而是正确性要求。无向图的另一个细节是i、j 的枚举只需做1 i j k。因为dist[i][j]和dist[j][i]对称环上 i、j 的位置可以互换枚举一半就够。如果写成1 i n, 1 j n结果虽然不会错但会产生大量重复计算。4. 路径回溯怎么把最小环原样打印出来求最小环长度只是第一步POJ 1734 还要求输出环上节点的访问顺序。这时就需要 Floyd 的路径回溯辅助数组。4.1 path 数组记录的是最后一个中转点经典的 Floyd 路径回溯是维护一个path[i][j]数组表示当前从 i 到 j 的最短路径上“最后一个被加入作为中转”的节点。在松弛时如果dist[i][j] dist[i][k] dist[k][j]说明通过 k 中转能让 i 到 j 更短于是更新距离同时记录path[i][j] k注意这个path[i][j]记录的只是“中转点”不是整条路径。真正的完整路径要靠递归一层层展开。初始时如果 i 和 j 之间有直接边dist[i][j]就是边的权值此时path[i][j]保持为 0表示“不需要再经过任何中间节点”。这里有个很容易混淆的细节不要把path和“下一个点”混淆。path[i][j]等于某个 k表示最短路径是i - ... - k - ... - j而不是i的下一个点就是 k。打印时需要考虑整个 i 到 k 以及 k 到 j 的子路径。4.2 递归展开路径的实现我习惯写一个辅助函数get_path(i, j)它负责把 i 到 j 最短路径上“除了 i 以外的节点”按顺序追加到答案序列中void get_path(int i, int j) { int k path[i][j]; if (k 0) { // 没有中间点直接相连 ans.push_back(j); return; } get_path(i, k); // 先处理 i 到 k 这一段 get_path(k, j); // 再处理 k 到 j 这一段 }当找到一个新的最小环假设是i - ... - j - k - i就按下面的顺序组装答案ans.clear(); ans.push_back(i); // 起点 get_path(i, j); // i 到 j 最短路径上的中间节点以及 j 本身 ans.push_back(k); // 再到 k // 环的最后一站是 k - i由原始边直接连接不需要打印重复的 i之所以不打印最后的 i是因为环的终点就是起点输出序列只写一遍起点即可。比如一个环是1 - 2 - 3 - 1输出1 2 3最后一个 1 表示回到起点不用再重复。4.3 路径回溯的小坑与调试技巧我在实现时踩过两个坑。第一个坑get_path的递归出口写错导致多打印一个节点。初始化时path[i][j] 0表示直接相连这个约定要和“i 到 j 不可达”区分开。如果一开始把path初始化为 -1那么在递归出口就要判断k -1再输出 j两种写法都行但不要混用。我上面给的是 0 约定配合初始化为全 0 的memset写起来最省事。第二个坑在无向图里dist[i][j]和dist[j][i]在松弛时是对称更新的所以path[i][j]和path[j][i]也应该保持对称。但如果你在写 Floyd 循环时只更新了i j的一半矩阵那么path[j][i]可能一直是 0回溯时就会出错。稳妥做法是循环里对完整 n*n 矩阵做更新不要为了省一半时间破坏对称性。调试时还有个技巧在get_path里临时加打印观察递归调用的顺序。一个最小环的节点数不多打印出递归过程很快就能发现是不是多输出或者漏输出某个点。5. 完整 AC 代码与实现细节5.1 参考实现下面这份代码是 C 版兼容 POJ 的老编译器环境没有用 C11 的特性。多组数据输入直到 EOF 为止。#include cstdio #include cstring #include vector #include algorithm using namespace std; const int MAXN 105; const int INF 0x3f3f3f3f; int n, m; int e[MAXN][MAXN]; int dist[MAXN][MAXN]; int path[MAXN][MAXN]; vectorint ans_route; int min_cycle; void get_path(int i, int j) { int k path[i][j]; if (k 0) { ans_route.push_back(j); return; } get_path(i, k); get_path(k, j); } void update_cycle(int i, int j, int k) { int sum dist[i][j] e[i][k] e[k][j]; if (sum min_cycle) return; min_cycle sum; ans_route.clear(); ans_route.push_back(i); get_path(i, j); ans_route.push_back(k); } void floyd() { for (int k 1; k n; k) { // 第 1 步找最小环 for (int i 1; i k; i) { for (int j i 1; j k; j) { if (e[i][k] INF || e[k][j] INF) continue; update_cycle(i, j, k); } } // 第 2 步用 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]; path[i][j] k; } } } } } int main() { while (scanf(%d%d, n, m) ! EOF) { memset(e, 0x3f, sizeof(e)); for (int i 1; i n; i) e[i][i] 0; for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); if (w e[u][v]) { e[u][v] e[v][u] w; // 无向图重边取最小 } } memcpy(dist, e, sizeof(e)); memset(path, 0, sizeof(path)); min_cycle INF; ans_route.clear(); floyd(); if (min_cycle INF) { puts(No solution.); } else { for (int i 0; i (int)ans_route.size(); i) { if (i 0) putchar( ); printf(%d, ans_route[i]); } putchar(\n); } } return 0; }5.2 实现细节说明这里挑几个我实际写题时反复确认过的点单独说说。第一INF用0x3f3f3f3f很合适。两个 INF 相加大约是0x7e7e7e7e仍然在 int 正数范围内不会溢出成负数。memset按字节填充0x3f也能直接得到这个值省事。第二重边必须处理。输入中两个景点之间可能有多条路我们只保留最短的一条。如果不做这个判断e[u][v]可能被后面的较长边覆盖导致最小环漏算。第三dist初始要从e拷贝一份而不能直接用e去参与 Floyd 更新。因为后面找环时还需要用到“原始直接边”e[i][k]和e[k][j]。如果你在 Floyd 过程中把e改掉了找环时就没有可靠的直接边信息了。第四环不存在的判断。如果整个图本来就不连通或者无法形成至少三个点的环min_cycle会一直停留在 INF输出No solution.。这个输出格式要注意题目对大小写和标点要求很严。5.3 复杂度分析与扩展思考时间复杂度上找环的枚举虽然在每轮 k 里只枚举了小于 k 的 i、j但总复杂度仍是 O(n^3) 级别Floyd 松弛主体也是 O(n^3)。n100 时两个 O(n^3) 加起来非常快运行时间完全不用担心。空间复杂度是 O(n^2)两个矩阵加一个 path 数组完全够用。这个模板不止能解这一题。如果题目要求“输出字典序最小的最小环”可以在更新环时增加序列比较如果是有向图的最小环枚举 i、j 时需要去掉i j的限制并且公式变为dist[i][j] e[j][k] e[k][i]这类闭合形式如果图中存在负权边就要额外考虑负权回路的问题了。最后分享一个我的做题习惯写完模板后不要直接交先手造三个小数据验证路径输出。第一个是简单的三角环例如 1-2、2-3、3-1 三条边权相等最小环显然就是 1-2-3第二个是带干扰边的图加一条不参与最小环的短线验证答案没有被干扰第三个是不存在环的图验证No solution.分支。这三组数据都能过再交 POJ 基本就稳了。