Sightseeing Trip 最小环

形式化题目

给定一张 $n$ 个点、 $m$ 条边的无向带权图（可能有重边），求一个至少包含 3 个点、点不重复的简单环，使环上边的长度之和最小；输出环上按顺序排列的点，最小环不唯一时输出任意一个，无解输出 No solution.。

样例图（1–3 之间实际有 300 和 10 两条边，图中只画最短的那条）：

graph LR
    n1((1)) ---|1| n4((4))
    n1 ---|10| n3((3))
    n1 ---|16| n2((2))
    n2 ---|100| n3
    n2 ---|15| n5((5))
    n3 ---|20| n5
    linkStyle 1,2,4,5 stroke:#e11d48,stroke-width:2px

最小环是 $1 \to 3 \to 5 \to 2 \to 1$ ，权值和 $10 + 20 + 15 + 16 = 61$ （图中加粗的四条边）。点 4 只与 1 相连、度为 1，不可能出现在任何环里。题面输出 1 3 5 2 与 main.py 实际输出的 2 1 3 5 是同一个环的不同起点——本题有 SPJ，起点与方向任意。

正解

思路

朴素做法：DFS 回溯枚举所有简单环并取最小。简单环的数量是指数级的， $n = 100$ 的稠密图完全跑不动。瓶颈在于环本身有指数多条，任何"把环逐个试"的框架都不可行，必须改写成"多项式个子问题，每个子问题一次查表/一次最短路"。

按最大编号点拆环：每个环都有唯一编号最大的点 $k$ 。在 $k$ 处把环断开，剩下的部分是一条 $i \to j$ 路径，其内部点编号全部小于 $k$ ，于是

\text{环长} = \text{dist}(i,\ j) + w(i,\ k) + w(k,\ j), \qquad i,\ j < k

枚举 $k$ 和端点对 $(i, j)$ 之后，问题变成："中间点编号严格小于 $k$ "的两点最短路。

用 Floyd 的阶段承接：Floyd 第 $k$ 轮松弛开始之前，dist[i][j] 恰好就是只允许经过 $0..k-1$ 的最短路，与拆环需要的受限最短路完全一致。所以每一轮的顺序是：

先探测：对 $i < j < k$ 且 $i, k$ 、 $k, j$ 都相邻的点对，用当前 $dist[i][j] + w(i,k) + w(k,j)$ 作为候选环，更优则记录；
再并入：做标准 Floyd 的 $k$ 阶段松弛，把 $k$ 变成允许的中间点。

先探测、后松弛的顺序不能换，这保证了探测时 dist 里还没有 $k$ 。任一环都在"它的最大点"那一轮被枚举到，而每个候选又都是合法环，两头夹逼即得最优。

输出方案：松弛时同步维护后继表 nxt[i][j] = nxt[i][k]（ $i$ 去 $j$ 的下一个点）。找到最优环后，从 $i$ 沿 nxt 回溯到 $j$ ，再接上 $k$ ，就得到按环上顺序的点序列。

下表展示样例中 Floyd 各轮的候选环（点编号从 1 起，dist 取该轮探测时的值）：

轮次 $k$	候选 $(i, j)$	候选环	环长	说明
3	$(1, 2)$	$1 \to 2 \to 3 \to 1$	$16 + 100 + 10 = 126$	$i, j$ 都与 3 相邻，直接成环
4	无	—	—	点 4 只与 1 相邻，凑不出 $i \to j \to 4 \to i$
5	$(2, 3)$	$2 \to 1 \to 3 \to 5 \to 2$	$26 + 15 + 20 = 61$	`dist(2,3) = 26` 走 $2 \to 1 \to 3$ ，更新最优

$k = 1, 2$ 时还没有两个更小的点，无候选。最终最优 61：回溯出路径 $2 \to 1 \to 3$ ，接上 $k = 5$ ，输出 2 1 3 5。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 14:30
# update_at: 2026-09-30 14:30

import sys

INF = 10 ** 12  # 无穷哨兵：环长是边权之和，不可能达到这个量级


def min_cycle(w: list[list[int]]) -> list[int]:
    """Floyd 最小环：以 k 为环上编号最大的点，用只经过编号 <k 的最短路 i→j 闭合成环。

    走到第 k 轮时 dist[i][j] 只经过 0..k-1，因此 i→j 的路径不含 k；再接上边
    (i,k)、(k,j) 就得到一个简单环。任一环都有唯一最大编号点，必在它那一轮被枚举到。
    返回环上依次的 1 编号节点；无环返回空表。
    """
    n = len(w)
    dist = [row[:] for row in w]  # dist[i][j]：中间点限制在 0..k-1 的最短路
    # 后继表：i 出发走向 j 的下一个点，用于把最短路还原成点序列
    nxt = [[j if w[i][j] < INF else -1 for j in range(n)] for i in range(n)]
    best = INF
    cycle: list[int] = []

    for k in range(n):
        # 第一步：先用「还没并入 k」的最短路找环，环 = i→…→j→k→i
        for i in range(k):
            if w[i][k] >= INF:
                continue  # i、k 不相邻，i→j→k 闭不回环
            for j in range(i + 1, k):
                # 边 (k,j) 不存在时 w[k][j]=INF，环长溢出到哨兵以上，自然不会更优
                cand = dist[i][j] + w[i][k] + w[k][j]
                if cand < best:
                    best = cand
                    path = [i]
                    while path[-1] != j:  # 沿后继表回溯 i→…→j
                        path.append(nxt[path[-1]][j])
                    cycle = path + [k]  # 按环上顺序：i→…→j→k，再回到 i

        # 第二步：把 k 并入最短路，供后续轮次使用
        for i in range(n):
            via_k = dist[i][k]
            if via_k >= INF:
                continue
            for j in range(n):
                if via_k + dist[k][j] < dist[i][j]:
                    dist[i][j] = via_k + dist[k][j]
                    nxt[i][j] = nxt[i][k]  # i 去 j 先迈向 i 的 k-后继

    return [x + 1 for x in cycle]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 邻接矩阵存边权：重边取最短（环上换用更短的平行边只会更优），自环凑不出 3 点环，忽略
    w = [[INF] * n for _ in range(n)]
    for i in range(n):
        w[i][i] = 0
    for _ in range(m):
        x, y, z = next(data) - 1, next(data) - 1, next(data)
        if x != y and z < w[x][y]:
            w[x][y] = w[y][x] = z

    cycle = min_cycle(w)
    print(' '.join(map(str, cycle)) if cycle else 'No solution.')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:18
 * update_at: 2026-10-05 04:18
 */

// 最小环 + 输出方案：以环上编号最大的点 k 拆环，
// 环长 = dist(i,j) + w(i,k) + w(k,j)，其中 dist 只允许经过编号 < k 的中间点。
// Floyd 第 k 轮松弛开始前，dist[i][j] 恰好就是这种受限最短路，
// 所以每轮先探测候选环，再做标准 Floyd 松弛；松弛时同步维护后继表用于还原路径。
// 无向图可能有重边：重边取最短；自环凑不出 3 点环，忽略。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;
const ll INF = 1e12; // 无穷哨兵：环长是边权之和，达不到这个量级

int n, m;
ll w[MAXN][MAXN];    // w[i][j]：i、j 之间最短边的权，不相邻为 INF
ll dist_[MAXN][MAXN]; // dist_[i][j]：中间点限制在编号 < k 的最短路（避开 std 的 dist 名字不必要，仅区分含义）
int nxt[MAXN][MAXN]; // 后继表：i 走向 j 的下一个点，用于把路径还原成点序列
ll best;             // 当前最小环长
int cyc[MAXN];       // 最优环上的点（1 编号），按环上顺序
int cyc_len;         // 环上点数

// 用后继表把 i -> j 的最短路回溯成点序列，再接上 k 闭合成环，存入 cyc[]
void record_cycle(int i, int j, int k) {
    int path[MAXN];
    int len = 0;
    path[len++] = i;
    while (path[len - 1] != j) {
        path[len] = nxt[path[len - 1]][j];
        len++;
    }
    cyc_len = 0;
    for (int t = 0; t < len; t++) cyc[cyc_len++] = path[t];
    cyc[cyc_len++] = k; // 按环上顺序：i -> ... -> j -> k，k 再回到 i
}

void solve() {
    // 初始化：dist 初始就是邻接矩阵；后继表初始为直达的下一个点
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist_[i][j] = w[i][j];
            if (w[i][j] < INF) nxt[i][j] = j; // i 直达 j，后继就是 j 本身
            else nxt[i][j] = -1;
        }
    }
    best = INF;
    cyc_len = 0;

    for (int k = 1; k <= n; k++) {
        // 第一步：用还没并入 k 的受限最短路探测候选环 i -> ... -> j -> k -> i
        for (int i = 1; i < k; i++) {
            if (w[i][k] >= INF) continue; // i、k 不相邻，闭不回环
            for (int j = i + 1; j < k; j++) {
                // w[k][j] 为 INF 时候选溢出，自然不会更优
                ll cand = dist_[i][j] + w[i][k] + w[k][j];
                if (cand < best) {
                    best = cand;
                    record_cycle(i, j, k);
                }
            }
        }

        // 第二步：标准 Floyd 的 k 阶段松弛，把 k 变成允许的中间点
        for (int i = 1; i <= n; i++) {
            if (dist_[i][k] >= INF) continue;
            for (int j = 1; j <= n; j++) {
                if (dist_[i][k] + dist_[k][j] < dist_[i][j]) {
                    dist_[i][j] = dist_[i][k] + dist_[k][j];
                    nxt[i][j] = nxt[i][k]; // i 去 j 先迈向 i 的 k-后继
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            w[i][j] = INF;
    for (int i = 1; i <= n; i++) w[i][i] = 0;
    for (int e = 1; e <= m; e++) {
        int x, y; ll z;
        cin >> x >> y >> z;
        if (x != y && z < w[x][y]) { // 重边取最短，自环忽略
            w[x][y] = z;
            w[y][x] = z;
        }
    }

    solve();

    if (cyc_len == 0) {
        cout << "No solution." << endl;
    } else {
        for (int t = 0; t < cyc_len; t++) {
            if (t) cout << ' ';
            cout << cyc[t];
        }
        cout << endl;
    }

    return 0;
}

复杂度

时间： $O(n^3)$ ——外层 $k$ 共 $n$ 轮，每轮探测与松弛各 $O(n^2)$ ； $n \leqslant 100$ 时约 $10^6$ 次操作，Python 实测最重数据约 0.04s。
空间： $O(n^2)$ ——边权 w、受限最短路 dist、后继 nxt 三张 $n \times n$ 矩阵。

总结

把"枚举环"改写成"枚举环上编号最大的点 $k$ "后，环就等于一条受限最短路加两条到 $k$ 的边；Floyd 的阶段不变量恰好是这种受限最短路，每轮先探测候选环、再把 $k$ 并入松弛，即可 $O(n^3)$ 求出最小环，并用后继表回溯出方案。重边取最小、自环忽略、无环输出 No solution. 是必须处理的边界。

Sightseeing Trip 最小环

目录

形式化题目

正解

思路

代码

复杂度

总结