目录
图论 - 最小环问题
可以利用 floyd 算法求最小环长度
floyd 算法有个性质：在最外层循环到点 k 时（尚未开始第 k 次循环），$d_{ij} $ 表示的是从 i 到 j 且仅经过编号 1 ~ k - 1 的点的最短路（即 $ \ge k $ 点的最短路尚未计算）。那么，我们设最小环中编号顶点最大的为 k ，环上与 k 相邻的两个点为 i ， j，则在最外层循环枚举到 k 时，该环的长度为 $ans = d_{ij} + d_{jk} + d_{ki} $。故在循环时对于每个 k 枚举满足 i < k 且 j < K 的点对(i,j)，同时更新答案即可
例题
无向图
利用floyd算法求解最小环的长度
代码
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*
*/
const int maxm = 1e2 + 5, inf = 5e8 + 5, mod = 998244353;
int n, m;
vector<vector<int>> g(maxm, vector<int>(maxm, inf)), c(maxm, vector<int>(maxm, inf));
void solve(){
cin >> n >> m;
for(int i = 0; i < m; ++ i){
int u, v, d;
cin >> u >> v >> d;
c[u][v] = c[v][u] = min(c[u][v], d);
g[u][v] = g[v][u] = min(g[u][v], d);
}
int ans = inf;
for(int k = 1; k <= n; ++ k){
for(int i = 1; i < k; ++ i){
for(int j = i + 1; j < k; ++ j){
ans = min(ans, g[i][j] + c[i][k] + c[k][j]);
}
}
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= n; ++ j){
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
if(ans == inf) cout << "No solution.\n";
else cout << ans << '\n';
return ;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}