P6175题解

发表于 更新于

P6175（数学化语言表述，较严谨且易理解）

考虑一个环：\(a_1- >a_2 ->a_3 ->…… ->a_n -> a_1\) \((n \ge 3)\)，设\(max(a_i)(1 \le i \le n) = a_k\)，设\(a_k\)在环中相邻的两个点分别是\(a_v\)和\(a_w\)。

对于任意的几个环，如果它们的\(a_k,a_v,a_w\)都分别相等，我们就把这几个环都放入一个集合，并设这个集合为 \(S(a_k,a_v,a_w)\)。

可以发现，任意一个环都属于一个集合。

令\(d(x,y)\)表示\(x\)和\(y\)之间直接距离（不经过其他点）。令\(f(x,y,k)\)表示x和y之间经过若干个编号\(<k\)的点得到的最短距离。

则易证，对于任意一个集合（设这个集合为\(S(a_k,a_v,a_w)\))，该集合中的最小环的长度为\(d(a_v,a_k) + d(a_k,a_w) + f(a_v,a_w,a_k)\)。

因为任意一个环都属于一个集合，所以我们只要枚举所有的集合，将该集合中最小环的长度作为可能的答案进行比较，即可得到最终答案。

现在还有一个问题，那就是如何求出\(f(a_v,a_w,a_k)\)。

我们可以发现\(floyd\)算法的外循环\(k\)枚举到\(a_k\)时，\(a_v,a_w\)之间的最短路径即为所求。

综上，时间复杂度\(O(n^3)\).

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

const int maxn = 105,maxm = 1e4 + 5,inf = 0x3f3f3f3f;

int n,m,vi,vj,vk,minn;
int f[maxn][maxn],v[maxn][maxn],a[maxn][maxn];
vector<int> path;

void work(int x,int y) {
	if (v[x][y] == 0)
		return;
	int tmp = v[x][y];
	work(x,tmp);
	path.push_back(tmp);
	work(tmp,y);	
}

int main() {
	scanf("%d %d",&n,&m);
	memset(f,0x3f,sizeof(f));
	memset(a,0x3f,sizeof(a));
	for (int i=1; i<=n; i++)
		f[i][i] = a[i][i] = 0;
		
	for (int i=1; i<=m; i++) {
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		if (x > n || y > n)
			continue;
		a[x][y] = min(a[x][y],z);
		a[y][x] = min(a[y][x],z);
		f[x][y] = min(f[x][y],z);
		f[y][x] = min(f[y][x],z);
	} 
	
	minn = inf;
	
	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)a[i][k] + a[k][j] + f[i][j] < (long long)minn) {
					minn = a[i][k] + a[k][j] + f[i][j];
					path.clear();
					path.push_back(i);
					path.push_back(k);
					path.push_back(j);
					work(j,i);
				}

			}
			
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++) {
				if (i == j || j == k || i == k)
					continue;
					
				if (f[i][j] > f[i][k] + f[k][j]) {
					f[i][j] = f[i][k] + f[k][j];
					v[i][j] = k;
				}
			}
	}
		
			
	if (minn == inf) {
		puts("No solution.");
		return 0;
	}
	
	for (int i=0; i<path.size(); i++)
		printf("%d ",path[i]);
	
	return 0;
}