算法思想

对于构成最小环的点集{x1, x2, …}，其中必定存在一个最大点xk，那么最小环的长度可以由dis[i][j]+m[j][xk]+m[xk][i]来表示，其中i，j均在点集中且小于xk，dis[i][j]是i到j的最短路径。因为xk是点集中最大的那个点，所以i到j的最短路径没有经过编号比xk更大的点。那么要求最小环的长度就可以由小到大枚举一下xk就行了。我们知道，floyd算法最外层每循环一次，就是由一个中间节点k更新点i到j的最短路径。k从小到大枚举，就保证了循环到k的时候，当前i到j的最短路经过的最大节点只可能是k，这刚好满足上面提到的dis[i][j]的定义。所以我们就可以愉快的使用floyd来求最小环了。

例题

vijos P1046 观光旅游

很裸的描述了，直接求最小环就好了。

Timus 1004. Sightseeing Trip

同上，不过要注意的就是，这个题目要求最小环的路径。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int MN = 110;
const int INF = 1e8;

int n, m, num, ans;
int mp[MN][MN], dis[MN][MN], pre[MN][MN];
int path[MN];

void get_path(int a, int b) {
    if (pre[a][b]) {
        get_path(a, pre[a][b]);
        get_path(pre[a][b], b);
    } else {
        path[num++] = a;
    }
}

int main() {
    while (scanf("%d", &n) && (n != -1)) {
        scanf("%d", &m);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                mp[i][j] = INF;
                dis[i][j] = INF;
                pre[i][j] = 0;
            }
        }
        int a, b, l;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &a, &b, &l);
            mp[a][b] = min(mp[a][b], l);
            mp[b][a] = dis[a][b] = dis[b][a] = mp[a][b];
        }
        ans = INF;
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i < k; i++)
                for (int j = i+1; j < k; j++) {
                    int tmp = dis[i][j] + mp[j][k] + mp[k][i];
                    if (tmp < ans) {
                        ans = tmp;
                        num = 0;
                        get_path(i, j);
                        path[num++] = j;
                        path[num++] = k;
                    }
                }

            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++) {
                    int tmp = dis[i][k] + dis[k][j];
                    if (dis[i][j] > tmp) {
                        dis[i][j] = tmp;
                        pre[i][j] = k;
                    }
                }
        }
        if (ans == INF) {
            cout << "No solution." << endl;
        } else {
            for (int i = 0; i < num; i++)
                printf("%d ", path[i]);
            cout << endl;
        }
    }
    return 0;
}