观光之旅

floyd 最小环问题 T4 344. 观光之旅 - AcWing题库 给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。

该问题称为无向图的最小环问题。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示无向图有 $N$ 个点，$M$ 条边。

接下来 $M$ 行，每行包含三个整数 $u，v，l$，表示点 $u$ 和点 $v$ 之间有一条边，边长为 $l$。

输出格式

输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 No solution.。

数据范围

$1\le N\le 100$,
$1\le M\le 10000$,
$1\le l<500$

输入样例：

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

思路

假设一条路径包含三个点 $(i,j,k)$, 满足下图： 这样定义就能包含所有点数大于等于3的环。我们需要找的是其中路径权值和最小的一个方案。

点数很少只有100个, 显然可以使用Floyd先求出每个点对于其他点的最短路径。但不能求完最短路再做, 因为在环中, $(i,j)$ 之间的路径不能经过$k$, 若求完再做, 显然 $(i,k,j)$ 这条路径有可能是结果, 但它并不是环。

故需要加一条限制, 让此时$(i,j)$的最短路不会经过$k$, 可以设定$k$是该条路径中序号最大的点, 这样就能保证是一条环。

之后再枚举路径$(i,j)$, 其中i和j都小于k, 然后算出加上k后的环的边权总和即可：

res = min(res, (long long)g[i][k] + g[k][j] + dist[i][j]);

这样可以求出最小环的边权大小, 不过这里题目是求出最小环的点编号, 也就是说需要记录路径。对于最小环 $(i,k,j)$ 我们只知道这三个点, 还需要得到 从 $i$ 到 $j$ 且不经过 $k$ 的一条路径。根据floyd求最短路的过程, 求$i,j$ 最短路时同样存在一个点 $k^{\prime }$（不一定是最大编号）, 且 $i,j$ 之间的最短路径经过 $k^{\prime }$, 因此我们可以在求最短路时存下每次更新$i,j$路径的$k^{\prime }$, 递归地求$i,j$ 路径, $i,k$ 和 $k,j$ 路径即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f, N = 1e2 + 50;
int g[N][N];
int dist[N][N];
int pos[N][N];
int path[N], cnt;
int n,m;
 
void getpath(int i, int j)
{
    if(pos[i][j] == 0) return;
    int k = pos[i][j];
    getpath(i,k);
    path[cnt++] = k;
    getpath(k,j);
}
 
 
int main()
{
    cin >> n >> m;
    memset(dist, 0x3f, sizeof dist);
    memset(g, 0x3f, sizeof g);
    for(int i = 1; i <= n; i ++) g[i][i] = 0, dist[i][i] = 0;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
        g[b][a] = min(g[b][a], c);
        dist[a][b] = min(dist[a][b], c);
        dist[b][a] = min(dist[b][a], c);
    }
    
    long long res = INF;
    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)g[i][k] + g[k][j] + dist[i][j] < res)
                {
                    res = g[i][k] + g[k][j] + dist[i][j];
                    cnt = 0;
                    path[cnt++] = i;
                    getpath(i,j);
                    path[cnt++] = j;
                    path[cnt++] = 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];
                    pos[i][j] = k;
                }
            
                
    }
    if(res == INF) cout << "No solution.\n";
    else {
        for(int i = 0; i < cnt; i++) cout << path[i] << " \n"[i == cnt-1];
    }
    return 0;
}