「poj 1734」Sightseeing trip (Floyd最小环)

poj 1734
给定一个无向图,求出节点数至少为$3$的最小环。输出方案

当Floyd中最外层循环到$k$,$dis(i,j)$则代表不经过大于等于$k$编号节点的最短路。

所以最小环我们可以枚举必过某个点的最小环是多少。即考虑过$k$点最小环,且只由不大于等于$k$编号节点的点组成。那么最小环即为

$$
\min_{1 \leq i < j < k}(dis(i,j)+a(i,k)+a(k,j))
$$

由于对称性,所以不会影响结果。
输出方案即根据DP转移来回溯答案。具体看代码实现。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int INF = 1000000000;
int n, m, G[305][305], a[305][305], pre[305][305];
vector<int > path;
void getpath(int x, int y) {
if (!pre[x][y]) return ;
getpath(x, pre[x][y]);
path.push_back(pre[x][y]);
getpath(pre[x][y], y);
}
void clean() {
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j) pre[i][j] = 0, a[i][j] = INF;
for (int i = 0; i <= n; ++i) a[i][i] = 0;
}
int solve() {
scanf("%d%d", &n, &m);
clean();
for (int x, y, v, i = 1; i <= m; ++i) {
scanf("%d%d%d", &x, &y, &v);
a[x][y] = a[y][x] = min(a[x][y], v);
}
memcpy(G, a, sizeof a);
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 (ans > (LL)G[i][j] + a[i][k] + a[k][j]) { // 3 个数相加
ans = G[i][j] + a[i][k] + a[k][j];
path.clear();
path.push_back(i), getpath(i, j), path.push_back(j), path.push_back(k);
}
}
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];
pre[i][j] = k;
}
}
}
if (ans == INF) return printf("No solution.\n"), 0;
for (int i = 0; i < (int)path.size(); ++i) printf("%d ", path[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
------ 本文结束 ------