【例 1】Sightseeing Trip（信息学奥赛一本通- P1494）（洛谷-P10927）

【题目描述】原题来自CEOI 1999给定一张无向图求图中一个至少包含 3 个点的环环上的节点不重复并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中你需要输出最小环的方案若最小环不唯一输出任意一个均可。若无解输出 No solution.。图的节点数不超过 100。【输入】第一行两个正整数 n,m 表示点数和边数。接下来 m 行每行三个正整数 x,y,z表示节点 x,y 之间有一条长度为 z 的边。【输出】输出一个最小环的方案按环上顺序输出最小环上的点。若最小环不唯一输出任意一个均可。若无解输出 “No solution.”。【输入样例】5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20【输出样例】1 3 5 21. 题意转换本题本质是在严格要求点不重复的前提下求解无向图的最小简单环并通过记录状态转移重构出该环的完整节点序列。2. 思考过程与解题思路直接结论基于的数据范围本题的唯一正解是时间复杂度为的Floyd 最小环算法。初始暴力 DFS 寻找简单环的思路时间复杂度在逻辑层面成立但在实际竞赛环境中必定面临严重超时。我们直接提取 Floyd 算法最外层循环的阶段性特征在最外层循环遍历到k时此时的g[i][j]严格代表只允许经过作为中转站的最短路径。这一特性天然隔离了节点 k使得我们可以通过枚举并引入原图的两条实边和来强制闭合一个无交叉的简单环。4. 算法设计与样例推演初始逻辑与参数设定完毕后标准流程应用如下双矩阵隔离利用存储绝对不更新的原图边长利用存储动态更新的最短路。环的闭合方程。即时快照与分治还原在sum被更新的瞬间立刻清空并使用getpath(i,j)递归压入中转点最后闭合节点k。样例推演极简面对样例中的 1, 2, 3, 5 构成的环。程序将跳过k1, 2, 3时的错误闭合尝试。当循环跃迁至k5时以g[2][3]为底座以d[2][5]和d[5][3]为支架精确命中最小环随后触发getpath的二叉树中序遍历依次输出2 1 3 5。5. 时空复杂度分析时间复杂度O(N^3)。Floyd 算法的三重循环固定执行次找环操作和次最短路更新操作对于的规模运算量在10^6级别1 秒内毫无压力。空间复杂度。邻接矩阵d、g及记录中转的path数组均只需的空间内存开销极小。6. 坑点与易错总结重边覆盖无向图读入时必须使用min(g[x][y],z)进行绝对边界拦截否则极易导致 WA。溢出陷阱三个未连通节点的无穷大之和可能越界。必须使用级别的long long。无解状态陷阱对未更新的sum进行大于号阈值拦截以防输出空数据。7. 代码进阶与优化剖析核心教学点在推导此题时许多同学会写出下方这段“仅仅错了一个测试点WA”的经典反例代码。它展示了考场上最容易踩中的两个高阶陷阱极具教学价值//会错一个测试点 得换方法 //这道题看到以后第一眼就是暴力 因为点数很少不超过100 //我们其实就是遍历每个节点看它能不能走一圈不重复的路回到自己 //如果能就把这个环记录下来 然后把长度也记录下来 //然后找到这个点走一圈回到自己的最短路 //接下来继续挨个节点作为起点进行遍历 如果走一圈不重复的路 //回到自己的长度比之前记录的小就更新 最后记录的一定是最小环 //但是这个一定会超时 我们就要想想别的办法 我们还是根据点数不超过100 //我们会想到这道题可能用O(n^3)的做法去做然后又是图上问题 //这个我们如果能想到floyd算法的性质 //这道题就能做出来了 //floyd算法最外层的循环k代表我们目前只允许经过编号为1……k的节点作为中转站 //那么当最外层循环刚好走到k 但还没有开始更新最短路的时候 //此时的g[i][j]代表的是只经过1……k-1这些节点作为中转从i到j的最短距离 //如果我们现在发现原图中i和k之间有一条边长度为d[i][k] //并且j和k之间也有一条边长度为d[k][j] //那么神奇的事情出现了 //从i走到j只经过k的点然后再从j直接走到k最后从k直接走回i //这刚好构成了一个完美的环 而且这个环里编号最大的节点恰好就是k //这个环的长度就是g[i][j]d[i][k]d[k][j] //因为g[i][j]里面绝对没有经过k因为当时只更新到了k-1 //所以这个环绝对不会有重复走过的点 //同时只要我们限制i和j不相等且都小于k 就能保证这个环至少包含3个点 #include iostream #include cmath #include algorithm using namespace std; int n,m; long long d[110][110];//点少所以选用邻接矩阵存图 存图的原始边长 long long g[110][110];//存floyd更新出来的最短路距离 int path[110][110];//path[i][j]代表i点到j点的最短距离需要经过哪个点中转 long long sum99999999999999;//存储最小环长度 struct node{ int a; int b; int c;//c一定是最小环的最后一个节点即c-a }tmp;//存储最短环的三个节点 a-b-c-a int vis[110];//标记一个点是否已经输出 //i为当前起点 j为当前终点 void dfs(int i,int j){ //如果i-j中间没有中转点了 就是最小单元 if(path[i][j]0){ if(vis[i]0){ couti ; vis[i]1; } if(vis[j]0){ coutj ; vis[j]1; } return; } //k这就是i和j的中转点 int kpath[i][j]; //然后继续[i,k]中转点 dfs(i,k); //然后继续[k,j]中转点 dfs(k,j); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //初始化所有点到点之间距离为无穷 for(int i1;in;i){ for(int j1;jn;j){ d[i][j]99999999999999; g[i][j]99999999999999; } } //建图 for(int i1;im;i){ int x,y; long long z; cinxyz; //无向图双向存边 g[x][y]min(g[x][y],z); g[y][x]min(g[y][x],z); d[x][y]min(d[x][y],z); d[y][x]min(d[y][x],z); } //接下来开始floyd更新最短路 for(int k1;kn;k){ //找环 for(int i1;ik;i){ for(int ji1;jk;j){ //如果当前已经保存的环长度大于当前环长度 if(sumg[i][j]d[i][k]d[k][j]){ //更新当前最小环长度 sumg[i][j]d[i][k]d[k][j]; //记录最小环的i j k点 tmp.ai; tmp.bj; tmp.ck; } } } //通过floyd更新最短路距离 for(int i1;in;i){ for(int j1;jn;j){ //如果i-k-j比i-j距离更短 就更新i-j的最短路 if(g[i][j]g[i][k]g[k][j]){ g[i][j]g[i][k]g[k][j]; //记录i-j要经过k点中转 path[i][j]k; } } } } //先处理无解情况 if(sum99999999999999){ coutNo solution.; return 0; } //接下来要输出路径 //前面保存的i-j的路径 其实可能i-j经过了很多地方 //我们要把它们一一输出出来 dfs(tmp.a,tmp.b); couttmp.c; return 0; }为什么这段代码会错最后一个测试点全局vis数组的路径污染试图用全局vis排重虽然巧妙但在k循环完毕后统一输出时最短路path矩阵可能已被后续更大的节点覆盖更新。在一条被污染的路径上做 DFSvis极易吞噬掉本该输出的合法节点。审视下方代码当前已从结构上解决了环路覆盖问题。优化剖析 1冗余变量剔除。代码中残留的struct node tmp和int vis[110]是前期调试的全局布尔去重机制遗留物。在当前的 Vector 递归体系下节点已由中序遍历自然排序无需记录末尾节点或进行访问标记直接删除可降低空间常数并提高代码可读性。优化剖析 2自反性对角线隐患。代码省去了d[i][i]0与g[i][i]0的对角线清零操作。虽然本题由于严格限制j i1绕过了自环干扰但在广义图论 DP 中缺失此初始化极易引起逻辑坍塌建议补齐。8. 完整代码#include iostream #include vector #include cmath #include algorithm using namespace std; int n,m; long long d[110][110];//点少所以选用邻接矩阵存图 存图的原始边长 long long g[110][110];//存floyd更新出来的最短路距离 int path[110][110];//path[i][j]代表i点到j点的最短距离需要经过哪个点中转 long long sum1e15;//存储最小环长度 vector int vec;//用来存最小环的所有点 //i为当前起点 j为当前终点 void getpath(int i,int j){ //如果i-j中间没有中转点了 就是最小单元直接相连 无须再分治 if(path[i][j]0){ return; } int kpath[i][j]; //二叉树中序遍历思想 保证输出顺序的绝对正确 左半段-根(k)-右半段 getpath(i,k); vec.push_back(k); getpath(k,j); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //初始化所有点到点之间距离为无穷 for(int i1;in;i){ for(int j1;jn;j){ d[i][j]1e15; g[i][j]1e15; } //【优化批注】此处建议补充d[i][i] 0; g[i][i] 0; //以杜绝其他复杂图模型中的自环干扰。 } //建图 for(int i1;im;i){ int x,y; long long z; cinxyz; //无向图双向存边 g[x][y]min(g[x][y],z); g[y][x]min(g[y][x],z); d[x][y]min(d[x][y],z); d[y][x]min(d[y][x],z); } //接下来开始floyd更新最短路 for(int k1;kn;k){ //找环 必须在更新最短路之前进行 此时g数组里绝对没有经过k的点 for(int i1;ik;i){ for(int ji1;jk;j){ //如果当前已经保存的环长度大于当前枚举的环长度 if(sumg[i][j]d[i][k]d[k][j]){ //更新当前最小环长度 sumg[i][j]d[i][k]d[k][j]; //清空之前存储的最小环的路径 vec.clear(); //存储最小环的路径上的起点 vec.push_back(i); //递归还原中转节点 getpath(i,j); //存储最小环的路径上的终点前点最后一个节点 vec.push_back(j); //存储最小环的路径上的终点 vec.push_back(k); } } } //通过floyd更新最短路距离 for(int i1;in;i){ for(int j1;jn;j){ //如果i-k-j比i-j距离更短 就更新i-j的最短路 if(g[i][j]g[i][k]g[k][j]){ g[i][j]g[i][k]g[k][j]; //记录i-j要经过k点中转 用于后续路径还原 path[i][j]k; } } } } //先处理无解情况 1e15浮点型用 比较更安全 if(sum1e14){ coutNo solution.; return 0; } //接下来要输出路径 for(int i0;ivec.size();i) coutvec[i] ; return 0; }