求无向图的最小环(大于等于三个节点):
在floyd的第k层未开始循环前,已经求解了所有i和j之间经过1~k-1的最短路径,为了按照环中的最大点来分类,枚举点k的所有临点i和j(i和j均小于k),如果i和j已经可达,那么i和j之间的点也只是1~k-1,满足环中最大点为k,此时环的值为k的两个临边和加上i和j的最短路径长度。
为了按顺序输出方案,可以把方案定为k~i~get_path(i,j)~j,这里的get_path是i和j的最短路中所有点(不包括i和j),在floyd循环中可以记录最后一个更新i和j距离的点,记为pos[i][j],那么get_path(i,j)可以用分治法,即get_path(i,j)=get_path(i,pos[i][j])+pos[i][j]+get_path(pos[i][j],j),当pos[i][j]==0时意味着i和j的最短路不经过其他点,那么按照get_path(i,j)的定义”i和j的最短路中所有点(不包括i和j)“,就可以直接返回了。
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
typedef long long ll;
int w[110][110], f[110][110];
vector<int> path;
int pos[110][110];
void get_path(int i, int j) {
if (pos[i][j] == 0)
return;
get_path(i, pos[i][j]);
path.push_back(pos[i][j]);
get_path(pos[i][j], j);
}
int main(void) {
int n, m;
cin >> n >> m;
memset(w, 0x3f, sizeof(w));
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
w[a][b] = min(w[a][b], c);
w[b][a] = min(w[b][a], c);
}
for (int i = 1; i <= n; i++)
w[i][i] = 0;
memcpy(f, w, sizeof(w));
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++) {
if ((ll)w[i][k] + w[k][j] + f[i][j] < ans) {
{
ans = w[i][k] + w[k][j] + f[i][j];
path.clear();
path.push_back(k);
path.push_back(i);
get_path(i, j);
path.push_back(j);
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
{
if (f[i][k] + f[k][j] < f[i][j]) {
f[i][j] = f[i][k] + f[k][j];
pos[i][j] = k;
}
}
}
}
}
if(path.size())
{
for (auto i : path)
cout << i << " ";
}
else
cout<<"No solution.\n";
return 0;
}