acw344

Floyd求无向图的最小环问题

#include<bits/stdc++.h>
using namespace std;
const int N = 110,M=10010,INF=0x3f3f3f3f;
int maxk[N][N];
int n, m;
int g[N][N];
int og[N][N];
int ans[N], cnt;
void track(int l, int r) {
	if (l==r||!maxk[l][r])return;
	int mid = maxk[l][r];
	track(l,mid);
	ans[++cnt] = mid;
	track(mid, r);


}
int main() {
	cin >> n >> m;
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= n; i++)g[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	memcpy(og, g, sizeof g);
	int res = INF;

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = i+1; j <= n; j++) {
				if (k != i && k != j) {//下面的ll一定要记得加，多个INF加起来会爆int
					if (res > (long long )g[i][j] + og[i][k] + og[k][j]) {
						res = g[i][j] + og[i][k] + og[k][j];
						cnt = 0;
						ans[++cnt] = k;
						ans[++cnt] = i;
						track(i, j);
						ans[++cnt] = j;
						
					}
				}
			}
		}
		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];
					maxk[i][j] = k;
				}
			}
		}
	}
	if (res == INF)puts("No solution.");
	else {
		for (int i = 1; i <= cnt; i++)cout << ans[i] << " ";
	}
}

Floyd求无向图的最小环问题