【题目描述】

【输入】

【输出】

【输入样例】

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 2

1. 题意转换

本题本质是在严格要求点不重复的前提下，求解无向图的最小简单环，并通过记录状态转移重构出该环的完整节点序列。

2. 思考过程与解题思路

直接结论：基于的数据范围，本题的唯一正解是时间复杂度为的Floyd 最小环算法。

初始暴力 DFS 寻找简单环的思路（时间复杂度）在逻辑层面成立，但在实际竞赛环境中必定面临严重超时。我们直接提取 Floyd 算法最外层循环的阶段性特征：在最外层循环遍历到k时，此时的g[i][j]严格代表只允许经过作为中转站的最短路径。这一特性天然隔离了节点 k，使得我们可以通过枚举并引入原图的两条实边（和）来强制闭合一个无交叉的简单环。

4. 算法设计与样例推演

初始逻辑与参数设定完毕后，标准流程应用如下：

1. 双矩阵隔离：利用存储绝对不更新的原图边长，利用存储动态更新的最短路。

2. 环的闭合方程：。

3. 即时快照与分治还原：在sum被更新的瞬间，立刻清空并使用getpath(i,j)递归压入中转点，最后闭合节点k。

样例推演（极简）：

面对样例中的 1, 2, 3, 5 构成的环。程序将跳过k=1, 2, 3时的错误闭合尝试。当循环跃迁至k=5时，以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 sum=99999999999999;//存储最小环长度 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){ cout<<i<<" "; vis[i]=1; } if(vis[j]==0){ cout<<j<<" "; vis[j]=1; } return; } //k这就是i和j的中转点 int k=path[i][j]; //然后继续[i,k]中转点 dfs(i,k); //然后继续[k,j]中转点 dfs(k,j); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; //初始化所有点到点之间距离为无穷 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ d[i][j]=99999999999999; g[i][j]=99999999999999; } } //建图 for(int i=1;i<=m;i++){ int x,y; long long z; cin>>x>>y>>z; //无向图双向存边 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 k=1;k<=n;k++){ //找环 for(int i=1;i<k;i++){ for(int j=i+1;j<k;j++){ //如果当前已经保存的环长度大于当前环长度 if(sum>g[i][j]+d[i][k]+d[k][j]){ //更新当前最小环长度 sum=g[i][j]+d[i][k]+d[k][j]; //记录最小环的i j k点 tmp.a=i; tmp.b=j; tmp.c=k; } } } //通过floyd更新最短路距离 for(int i=1;i<=n;i++){ for(int j=1;j<=n;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(sum==99999999999999){ cout<<"No solution."; return 0; } //接下来要输出路径 //前面保存的i->j的路径 其实可能i->j经过了很多地方 //我们要把它们一一输出出来 dfs(tmp.a,tmp.b); cout<<tmp.c; return 0; }

为什么这段代码会错最后一个测试点？

1. 全局vis数组的路径污染：试图用全局vis排重虽然巧妙，但在k循环完毕后统一输出时，最短路path矩阵可能已被后续更大的节点覆盖更新。在一条被污染的路径上做 DFS，vis极易吞噬掉本该输出的合法节点。

审视下方代码，当前已从结构上解决了环路覆盖问题。

• 优化剖析 1：冗余变量剔除。代码中残留的struct node tmp和int vis[110]是前期调试的全局布尔去重机制遗留物。在当前的 Vector 递归体系下，节点已由中序遍历自然排序，无需记录末尾节点或进行访问标记，直接删除可降低空间常数并提高代码可读性。

• 优化剖析 2：自反性对角线隐患。代码省去了d[i][i]=0与g[i][i]=0的对角线清零操作。虽然本题由于严格限制j = i+1绕过了自环干扰，但在广义图论 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 sum=1e15;//存储最小环长度 vector <int> vec;//用来存最小环的所有点 //i为当前起点 j为当前终点 void getpath(int i,int j){ //如果i->j中间没有中转点了 就是最小单元（直接相连 无须再分治） if(path[i][j]==0){ return; } int k=path[i][j]; //二叉树中序遍历思想 保证输出顺序的绝对正确 左半段->根(k)->右半段 getpath(i,k); vec.push_back(k); getpath(k,j); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; //初始化所有点到点之间距离为无穷 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ d[i][j]=1e15; g[i][j]=1e15; } //【优化批注】：此处建议补充d[i][i] = 0; g[i][i] = 0; //以杜绝其他复杂图模型中的自环干扰。 } //建图 for(int i=1;i<=m;i++){ int x,y; long long z; cin>>x>>y>>z; //无向图双向存边 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 k=1;k<=n;k++){ //找环 必须在更新最短路之前进行 此时g数组里绝对没有经过k的点 for(int i=1;i<k;i++){ for(int j=i+1;j<k;j++){ //如果当前已经保存的环长度大于当前枚举的环长度 if(sum>g[i][j]+d[i][k]+d[k][j]){ //更新当前最小环长度 sum=g[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 i=1;i<=n;i++){ for(int j=1;j<=n;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(sum>1e14){ cout<<"No solution."; return 0; } //接下来要输出路径 for(int i=0;i<vec.size();i++) cout<<vec[i]<<" "; return 0; }