周游加拿大

题意

给定 $N \le 100$ 个城市（已按自西向东编号）和 $V$ 条双向直达航线，找一条从最西边城市（编号 0）出发、经过每个城市至多一次（起点除外，起点出现两次）的闭合旅行路线，使访问的不同城市数最多。输出该最大值；一条路线都找不到时输出 1。

旅行路线的形状：先自西向东走到最东边城市，再自东向西折返——去程和回程方向一致（自西向东），且两条路径除起点外不共用任何城市。

flowchart LR
    S((0\n起点)) --> a((a)) --> n1((n-1\n终点))
    S --> b((b)) --> n1

思路

朴素思路：直接在图上 DFS 找最长简单环。环的形态被两个约束绑死——

环必须经过编号最小的城市 0；
环上的边必须能拆成两条编号严格递增的链，两条链只在 0 和 $n-1$ 处汇合。

为什么必须递增？环从 0 出发先走「去程」到最东边、再走「回程」回来，两段路的走向都是自西向东（回程是逆向走的，但从 0 的视角看依然是从西往东编号递增的另一个分支）。因此整个环其实就是两条从 0 到 $n-1$ 的、中间点互不相同的上升路径拼起来的闭合曲线。

朴素 DFS 的状态空间太大（同一个点可能以「去程经过 / 回程经过」两种身份出现，无法用简单的 visited 排重），需要换成成对 DP。

状态设计：设 dp[a][b]（ $a \le b$ ）= 去程当前停在城市 $a$ 、回程当前停在城市 $b$ 时，已被这两条链覆盖的不同城市数（计入起点 0，暂不计终点 $n-1$ ）。

状态转移：扩展两条链中「编号较小」的那个端点，保证它永远跳到比 $\max(a,b)$ 更大的城市，避免回头或越过另一条链的端点。

扩展去程 $a \to c$ ：要求 $c > \max(a,b)$ 且 $a$ 与 $c$ 之间有边，转移到 dp[c][b] = dp[a][b] + 1；
扩展回程 $b \to c$ ：要求 $c > b$ 且 $b$ 与 $c$ 之间有边，转移到 dp[c][a] = dp[a][b] + 1（去程端点 $a$ 与新端点 $c$ 比较后交换顺序）。

注意 $a = b$ 的中间态没有意义——两条链在中间汇合意味着它们共享了一个非起终点城市，违反「每城只访问一次」。所以除初始态 dp[0][0] = 0 外，DP 过程中只允许 $a < b$ 的状态存活。

闭合答案：当两条链都抵达终点（或一条已抵达、另一条停在 $b$ 且 $b$ 与终点相邻）时，加上终点本身这个城市，得到环大小：

去程停 $n-1$ 、回程停 $b < n-1$ 且 $(b, n-1)$ 有边： $ans = dp[n-1][b] + 1$ ；
$n = 1$ 特判：答案为 1。

复杂度：状态 $O(N^2)$ ，每个状态向后扩展 $O(N)$ 个城市，总复杂度 $O(N^3)$ ； $N \le 100$ 时约 $10^6$ 量级，远在时限内。

样例可视化

以样例输入（8 城 9 边）为例，最优环为 Vancouver → Edmonton → Montreal → Halifax → Toronto → Winnipeg → Calgary → Vancouver，把它拆成两条上升链：

链	路径（按城市编号递增）	对应 dp 维度
去程（A 链）	0 (Vancouver) → 2 (Edmonton) → 6 (Montreal)	dp[a][b] 的 a
回程（B 链）	0 (Vancouver) → 3 (Calgary) → 4 (Winnipeg) → 5 (Toronto) → 7 (Halifax)	dp[a][b] 的 b

flowchart LR
    V0((Vancouver\n0)) --> E2((Edmonton\n2)) --> M6((Montreal\n6)) --> H7((Halifax\n7))
    V0 --> C3((Calgary\n3)) --> W4((Winnipeg\n4)) --> T5((Toronto\n5)) --> H7
    style V0 fill:#ffd
    style H7 fill:#ffd

DP 过程（列出关键状态，城市用编号表示；dp 值不含终点 Halifax=7，闭合时 +1 补回）：

dp 状态 `(a, b)`	含义	覆盖城市数（不含终点）
`(0, 0)`	两条链都还在起点	0
`(2, 3)`	去程到 Edmonton、回程到 Calgary	3
`(6, 3)`	去程到 Montreal、回程仍在 Calgary	3
`(6, 4)`	去程到 Montreal、回程到 Winnipeg	4
`(6, 5)`	去程到 Montreal、回程到 Toronto	5
`(7, 5)`	去程到终点 Halifax、回程到 Toronto	6
闭合 `(7,5) → +1`	回程从 Toronto 直达终点 Halifax，补上 Halifax	7

最终 best = dp[7][5] + 1 = 7，与样例输出一致。

代码

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"""周游加拿大: 双向扩位 DP, 两条不交单调链闭环成最长大环 — O(N^3)"""
import sys


def main() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, v = int(next(data)), int(next(data))
    names = [next(data) for _ in range(n)]
    idx: dict[str, int] = {s: i for i, s in enumerate(names)}
    # 邻接矩阵 (城市已按自西向东编号 0..n-1)
    adj: list[list[bool]] = [[False] * n for _ in range(n)]
    for _ in range(v):
        x, y = next(data), next(data)  # 航线两端的城市名
        a, b = idx[x], idx[y]
        adj[a][b] = adj[b][a] = True

    # dp[a][b] (a<=b): 去程停 a / 回程停 b, 覆盖城市数 (不含终点 n-1, 计入起点 0)
    # 合法分解要求除 0 和 n-1 外点不交, 故 a==b 的中间态无意义, 只留 dp[0][0]
    NEG = -10**9
    dp: list[list[int]] = [[NEG] * n for _ in range(n)]
    dp[0][0] = 0
    for a in range(n):
        for b in range(n):
            cur = dp[a][b]
            # 无效态 / 中途 a==b / 两条链都已抵达终点: 不再扩展
            if cur < 0 or (a == b and a != 0) or (a == n - 1 and b == n - 1):
                continue
            t = cur + 1
            row = adj[a]  # 去程前进: a -> c
            for c in range(max(a, b) + 1, n):
                if row[c] and t > dp[c][b]:
                    dp[c][b] = t
            row = adj[b]  # 回程前进: b -> c
            for c in range(b + 1, n):
                if row[c] and t > dp[c][a]:
                    dp[c][a] = t

    # 闭合: 回程停 b 且 b 与终点相邻 -> 去程已在终点, +1 补上终点本身
    best = 0
    last = adj[n - 1]
    for b in range(n - 1):
        if dp[n - 1][b] >= 0 and last[b]:
            best = max(best, dp[n - 1][b] + 1)
    print(max(best, 1))


main()

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/**
 * 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-06 12:33
 * update_at: 2026-10-06 12:33
 */
#include <iostream>
#include <map>
#include <string>
using namespace std;

const int MAXN = 105;
const int NEG = -1000000000;

typedef long long ll;

ll n, v;
map<string, int> name_id; // 城市名 -> 自西向东的编号 0..n-1
int adj[MAXN][MAXN];      // 邻接矩阵，adj[i][j]=1 表示城市 i、j 之间有直达航线
int dp[MAXN][MAXN];       // dp[a][b]: 去程停在 a、回程停在 b 时覆盖的城市数(不计终点 n-1)

void read_input() {
    cin >> n >> v;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        name_id[s] = i;
    }
    for (int i = 0; i < v; i++) {
        string x, y;
        cin >> x >> y;
        int a = name_id[x];
        int b = name_id[y];
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
}

void solve() {
    if (n == 1) {
        cout << 1 << '\n';
        return;
    }

    for (int a = 0; a < n; a++) {
        for (int b = 0; b < n; b++) {
            dp[a][b] = NEG;
        }
    }
    dp[0][0] = 0; // 两条链都还在起点 0，只计起点这一个城市

    for (int a = 0; a < n; a++) {
        for (int b = 0; b < n; b++) {
            int cur = dp[a][b];
            // 无效态；两条链在非起点处汇合；两条链都到达终点，均不再扩展
            if (cur < 0 || (a == b && a != 0) || (a == n - 1 && b == n - 1)) {
                continue;
            }
            int nxt = cur + 1;
            int far = a > b ? a : b; // 两条链端点中较大的编号
            // 去程前进：a -> c，c 必须比两条链的所有端点都大，避免重复覆盖
            for (int c = far + 1; c < n; c++) {
                if (adj[a][c] && nxt > dp[c][b]) {
                    dp[c][b] = nxt;
                }
            }
            // 回程前进：b -> c
            for (int c = b + 1; c < n; c++) {
                if (adj[b][c] && nxt > dp[c][a]) {
                    dp[c][a] = nxt;
                }
            }
        }
    }

    // 闭合：去程已到终点 n-1，回程停在 b 且 b 与终点相邻，补上终点这一个城市
    int best = 0;
    for (int b = 0; b < n - 1; b++) {
        if (dp[n - 1][b] >= 0 && adj[n - 1][b]) {
            if (dp[n - 1][b] + 1 > best) {
                best = dp[n - 1][b] + 1;
            }
        }
    }
    if (best < 1) {
        best = 1; // 一条路线都找不到时，题目规定输出 1
    }
    cout << best << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间： $O(N^3)$ —— $N^2$ 个状态，每个状态 $O(N)$ 次转移。
空间： $O(N^2)$ —— 邻接矩阵 + dp 表。

边界与陷阱

$a = b$ 状态非法：两条链在中间汇合即共享中间城市，必须禁止（起点 0 除外），否则会像两条链「合体」一样重复计数、得出偏大的答案。
转移的扫描范围：去程扩展时新城市 $c$ 必须大于 $\max(a,b)$ ，否则会越过另一条链的端点，造成同一城市被两条链同时覆盖。
闭合时 +1：dp 值不含终点 $n-1$ ，最后闭合环时要把终点这个城市补上。
无解特判：输出 1（题目规定的兜底值）。