<—点个赞吧QwQ

宣传一下算法提高课整理

给定一张无向图，求图中一个至少包含 $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

思路

这题思路懂了，其实很简单。双倍经验？
我们可以把一个环，拆成有三个点的链的长度$+$链头上的两个点的最短距离，但是$\text{Floyd}$会把所有的点都更新成最短距离。所以我们就可以枚举链的中间点，剩下的相邻点可以到这个点的距离和和$k$相邻的点之间的最短路可以构成一个环。然后以$k$为中心再次更新整个图的最短路。
感性的理解一下吧。

代码

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110,INF = 0x3f3f3f3f;
int n,m,cnt;
int g[N][N],d[N][N];
int p[N][N];
vector <int> path;
void getPath (int i,int j) {
    int k = p[i][j];
    if (k == 0) return ;
    getPath (i,k);
    path.push_back (k);
    getPath (k,j);
}
int main () {
    cin >> n >> m;
    memset (g,0x3f,sizeof (g));
    for (int i = 0;i <= n;i++) g[i][i] = 0;
    while (m--) {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min (g[a][b],c);
    }
    int ans = INF;
    memcpy (d,g,sizeof (d));
    for (int k = 1;k <= n;k++) {
        for (int i = 1;i <= k - 1;i++) {    //  这里为什么是 k - 1 解释一下：涉及到 Floyd DP 方程的本质，以 k 为阶段更新最短路数组，更新前最短路不可能经过点 k，故达到了我们想要的目的
            for (int j = i + 1;j <= k - 1;j++) {
                if ((LL)g[i][j] + d[i][k] + d[k][j] < ans) {
                    ans = g[i][j] + d[i][k] + d[k][j];
                    cnt = 0;
                    path.clear ();
                    path.push_back (k);
                    path.push_back (i);
                    getPath (i,j);
                    path.push_back (j);
                }
            }
        }
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) {
                if (g[i][j] > g[i][k] + g[k][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                    p[i][j] = k;
                }
            }
        }
    }
    if (ans == INF) puts ("No solution.");
    else {
        for (int x : path) cout << x << ' ';
        cout << endl;
    }
    return 0;
}