Acwing 344.观光之旅
题意
给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。
你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。
1 ≤ N ≤ 100 ,
1 ≤ M ≤ 10000 ,
1 ≤ l < 500
思路
将所有环 按照环上最大的点的编号 分成n类，1,2,3…,n-1,n
对于Floyd 的三重循环
for(k=1->n) for(i=1->n) for(j=1->n)
可以知道当最外层循环到第 k 轮时，代表第 k 类环，即环上的点的编号最大为 k，因为此时所有最短路只被 1 ∼ k − 1 松弛过
这样一类环可以表示成下述形式：
所以第k类的环的距离可以表示成 d[i][j] + g[i][k] + g[k][i] ，其中d为最短路径数组，
对每一类环枚举小于 k 的每两个点对（因为环上最大的点为 k），取min即可得到答案。
本题需要求具体方案，
在floyd 算法中，存在一个三角不等式 d[i][j] >= d[i][k] + d[k][j]
当某一 k 满足 d[i][j] = d[i][k] + d[k][j] 时，说明 k可以使得 从 i 到 j 的距离最小，那么 从 i 到 j 的最短路径一定包含 k，我们用 pos[i][j] = k 表示，i - j 的路径是从 k 更新过去的。
所以对于从 i - j 的最短路径，可以通过递归的方法求出经过的所有点。
最短路径上的点加上之前叙述的 环上的 k ，即为环上的所有点。
代码
// Author：zzqwtcc // Problem: 观光之旅 // Contest: AcWing // Time：2021-10-18 22:04:48 // URL: https://www.acwing.com/problem/content/346/ // Memory Limit: 64 MB // Time Limit: 1000 ms #include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; #define endl '\n' using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 110; int n, m; int g[N][N],d[N][N]; int path[N],cnt; int pos[N][N]; void get_path(int i,int j){ if(pos[i][j] == 0)return ; int k = pos[i][j]; get_path(i,k); path[cnt++] = k; get_path(k,j); } void solve() { cin >> n >> m; memset(g,0x3f,sizeof g); rep(i,1,n)g[i][i] = 0; while(m--){ int a,b,c;scanf("%d%d%d",&a,&b,&c); g[a][b] = g[b][a] = min(g[a][b],c); } memcpy(d,g,sizeof d); int 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((LL)d[i][j] + g[j][k] + g[k][i] < res) { res = d[i][j] + g[i][k] + g[k][j]; cnt = 0; path[cnt++] = k; path[cnt++] = i; get_path(i,j); path[cnt++] = j; } } } for(int i = 1; i <= n;++i){ for(int j = 1; j <= n;++j){ if(d[i][j] > d[i][k] + d[k][j]){ d[i][j] = d[i][k] + d[k][j]; pos[i][j] = k; } } } } if(res == INF)puts("No solution."); else { for(int i =0 ; i < cnt;++i){ printf("%d ",path[i]); } cout << endl; } } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
