ACWing 344 观光之旅题解

y0k1n0

2025 年 03 月 20 日

123 次浏览

暂无评论

1714字数

动态规划思维搜索

# 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 日