Acwing_344观光之旅【Floyd应用: 最小环】

题目链接:

思路分析: 1.本题的思路就是考虑最小环里面节点编号最大的节点为k,且环里面与k相连的两个点为i，j，环的长度为g[i][k]+g[k][j]+d[j][i];

2.则d[j][i]则表示j到i且经过的节点编号小于k,因为在环中k就是最大的，只能经过小于k的节点了;

3.则这与floyd中k次循环开始前的d[i][j]意义相同;

4.那就不妨在floyd的第一重循环就求一下以k为最大节点编号的环的长度，注意这里的k必须与节点的意义一样：0-n-1或1-n;

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N][N], g[N][N];
int pos[N][N];
int path[N], cnt;

void get_path(int i, int j)
{
          
   
	if (pos[i][j] == 0) return;
	int k = pos[i][j];
	get_path(i, k);
	path[cnt++] = k;
	get_path(k, j);
}

int main()
{
          
   
	cin >> n >> m;
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= n; i++) g[i][i] = 0;

	while (m--)
	{
          
   
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	int res = INF;
	memcpy(d, g, sizeof d);
	for (int k = 1; k <= n; k++)
	{
          
   
		for (int i = 1; i < k; i++) {
          
   
			for (int j = i + 1; j < k; j++) {
          
   
				if ((long long)d[i][j] + g[j][k] + g[k][i] < res)
				{
          
   
					res = d[i][j] + g[j][k] + g[k][i];
					cnt = 0;
					path[cnt++] = k;
					path[cnt++] = i;
					get_path(i, j);//将i到j的中间点存放到path数组中 
					path[cnt++] = j;
				}
			}
		}
		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 (res == INF) puts("No solution.");
	else {
          
   
		for (int i = 0; i < cnt; i++) {
          
   
			printf("%d ", path[i]);
		}
	}

	system("pause");
	return 0;
}