Loading... # ACWing 344 观光之旅 题解 ## 题目描述 给定一张无向图，求图中一个至少包含$3$个点的环，环上的节点不重复，并且环上的边的长度之和最小。 该问题称为无向图的最小环问题。 你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。 ## 输入 第一行包含两个整数$N$和$M$，表示无向图有$N$个点，$M$条边。 接下来$M$行，每行包含三个整数$u，v，l$，表示点$u$和点$v$之间有一条边，边长为 $l$。 ## 输出 输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 `No solution.`。 ## 解题思路 由于本题需要求得环上所有边的最小值， 因此不难想到首先需要求出所有节点之间的最短路程， 因此需要Floyd算法。 下面考虑如何枚举所有的环， 并求得环上的最小值： - 由于之前已经用Floyd算法求出了所有的从$i$到$j$的最小值， 因此只需要在找到一个点$k$，满足$k$不在从$i$到$j$的最短路上，且从$i$经过$k$可以到的$j$， 利用这两条路线即可更新最短环`dp[k][i][j]` - 显然上面的枚举方式可以覆盖所有的环线， 但是这样子枚举会存在很多的冗余计算，而且不容易进行枚举$k$，因此考虑优化上述的枚举方式 - 分析不难发现，枚举难度大的原因是我在确定了$i$和$j$的情况下想要去找$k$，而又没有办法在一个较低的时间复杂度下找到$k$的所有取值， 因此找到一个优化的切入点， 如果可以在$k$确定的情况下找到可能的$i$和$j$的取值就可以让枚举变得简单。 - Floyd就提供了这样一个思路， Floyd算法在动态更新`dist`数组时， 从图论的角度可以看作维护了一个从节点$i$经过节点$k$走到节点$j$的最小值; - 不难发现， 当$k = x$时， 对于所有的$i, j < k$,当前`dist`数组所遍历过的状态中一定不存在一条从$i$出发经过$y$到达$j$的路径， 其中$y > x$， 如果此时对于$y > k$，存在两条边 `edge[i][y], edge[y][j]`， 则此时一定可以构成环。 - 因此我们可以用这个性质， 来动态枚举所有$i, j < k$的情况下， `dist[i][j]+g[i][k]+g[j][k]`作为环的路径长度 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #define endl '\n' using namespace std; const int N = 520; int n, m; int dist[N][N], g[N][N]; int rec[N][N]; int ans = 0x3f3f3f3f; int chain[N], idx; void dfs(int i, int j) { int k = rec[i][j]; if(k == 0) return; dfs(i, k); chain[++ idx] = k; dfs(k, j); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(g, 0x3f, sizeof g); cin >> n >> m; for(int i = 1; i <= n; i ++) g[i][i] = 0; for(int i = 1; i <= m; i ++) { int x, y, z; cin >> x >> y >> z; g[x][y] = min(g[x][y], z); g[y][x] = min(g[y][x], z); } memcpy(dist, g, sizeof g); for(int k = 1; k <= n; k ++) { for(int i = 1; i < k; i ++) { for(int j = i + 1; j < k; j ++) { if((long long)dist[i][j] + g[i][k] + g[k][j] < ans) { ans = dist[i][j] + g[i][k] + g[k][j]; idx = 0; chain[++ idx] = j; chain[++ idx] = k; chain[++ idx] = i; dfs(i, j); } } } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { if(dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; rec[i][j] = k; } } } } if(ans == 0x3f3f3f3f) cout << "No solution." << endl; else { for(int i = 1; i <= idx; i ++) cout << chain[i] << ' '; } return 0; } ``` 最后修改：2025 年 03 月 20 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏