344. 观光之旅（最小环问题，Floyd）

344. 观光之旅 - AcWing题库

给定一张无向图，求图中一个至少包含?33?个点的环，环上的节点不重复，并且环上的边的长度之和最小。

该问题称为无向图的最小环问题。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

输入格式

第一行包含两个整数?N?和?M，表示无向图有?N?个点，M?条边。

接下来?M?行，每行包含三个整数?u，v，l，表示点?u?和点?v?之间有一条边，边长为?l。

输出格式

输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出?No solution.。

数据范围

1≤N≤100
1≤M≤10000
1≤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

解析：?

考虑Floyd算法的过程，当外层循环k刚开始时，d[i,j]保存着“经过编号不超过k-1的节点“从i到j的最短路。

于是，min{d[i,j]+a[j,k]+a[k,i]}其中1<=i<j<k，就是满足以下条件的最小环长度。

1.有编号不超过k的节点构成

2.经过节点k

上式中的i，j相当于枚举了环上与k相邻的两个点。古以上结论显然成立。存在k属于[1,n],都对上式进行计算，取最小值，即可得到整张图的最小环。

?拓展（对于有向图的最小环问题）：
对于有向图的最小环问题，可以枚举起点S=1~n,执行堆优化版Dijkstra算法求解单源最短路径。S一定是第一个被从堆中取出的节点，我们扫描S的所有边，当拓展、更新完成后，令d[S]=INF，然后继续求解。当S第二次被从堆中取出时，d[S]就是经过点S的最小环长度。

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 105;
int n, m;
int g[N][N], d[N][N];
int pos[N][N];
vector<int>path;

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() {
	cin >> n >> m;
	memset(g, 0x3f, sizeof g);
	for (int i = 1,a,b,c; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	memcpy(d, g, sizeof d);

	int ans = 0x3f3f3f3f;
	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[i][k] + g[k][j] < ans) {
					ans = d[i][j] + g[i][k] + g[k][j];
					path.clear();
					path.push_back(i);
					get_path(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 (d[i][j] > d[i][k] + d[k][j]) {
					d[i][j] = d[i][k] + d[k][j];
					pos[i][j] = k;
				}
			}
		}
	}
	if (ans == 0x3f3f3f3f)cout << "No solution." << endl;
	else {
		for (int i = 0; i < path.size(); i++) {
			printf("%d ", path[i]);
		}
		cout << endl;
	}
	return 0;
}