[CSP-S 2022] 假期计划

GitHub跳转原题关系图返回列表

先 BFS 求限制步数内可达，再为每个点保留前 4 个高分候选，枚举中间两个景点凑出四段行程。

OJ: luogu

题目 ID: P8817

难度:提高+/省选-

标签:图论BFS枚举贪心

创建: 2026-07-06 08:46

更新: 2026-10-07 12:15

前置题目

luogu P8605[蓝桥杯 2013 国 AC] 网络寻路B 复用 A 教的「固定中间一段、两端独立选」这一步分解（先定 B→C 再两侧各选一个），只是把邻居计数换成 BFS 可达矩阵+每侧 top3 分数候选枚举，再叠加 A 未教的可转车 k 次可达预处理与四景点互不相同的约束处理。

形式化题目

给定一张 $n$ 个结点的无向图，结点 $1$ 是家，结点 $2\sim n$ 是景点，景点 $i$ 有分数 $s_i$ 。

两个结点 $x,y$ 可转车 $k$ 次通达，指 $x$ 到 $y$ 的简单路径边数不超过 $k+1$ 。

要求选四个互不相同的景点 $A,B,C,D$ ，使得

1\to A\to B\to C\to D\to 1

这五段行程都可转车 $k$ 次通达，并最大化

s_A+s_B+s_C+s_D.

保证至少存在一组符合要求的行程。

样例 $1$ 是一个 $8$ 个结点的环， $k=1$ ，即每段行程最多走 $2$ 条边。

flowchart LR
  N1["1 家"] --- N2["2: 9"]
  N2 --- N3["3: 7"]
  N3 --- N4["4: 1"]
  N4 --- N5["5: 8"]
  N5 --- N6["6: 2"]
  N6 --- N7["7: 3"]
  N7 --- N8["8: 6"]
  N8 --- N1

最优行程是 $2\to3\to5\to7$ ，对应 $9+7+8+3=27$ 。

暴力解法

思路

先用 BFS 求出 can_reach[x][y]，表示 $x$ 到 $y$ 是否可转车 $k$ 次通达。然后直接枚举四个互不相同的景点 $A,B,C,D$ ，逐段检查

1\to A,\ A\to B,\ B\to C,\ C\to D,\ D\to 1

是否都可达，可行就更新分数和的最大值。

代码

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/**
 * 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-01 22:21
 * update_at: 2026-10-01 22:21
 */
// brute.cpp：小数据暴力解，枚举 4 个不同景点并检查 5 段行程是否都能在限制内通达。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 25;   // 暴力只服务小数据，n 取到 20 左右

int n, m, k;
ll score[MAXN];                // score[i]：景点 i 的分数
vector<int> graph_edges[MAXN]; // graph_edges[u]：与 u 有直达线路的点
bool can_reach[MAXN][MAXN];    // can_reach[x][y]：x 到 y 是否最多转车 k 次
int dist[MAXN];                // BFS 距离数组

// 从 start 出发做 BFS，标记 k+1 条边以内可达的点。
void bfs(int start) {
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        can_reach[start][u] = true;
        if (dist[u] == k + 1) {
            continue;
        }

        int cnt = graph_edges[u].size();
        for (int i = 0; i < cnt; i++) {
            int v = graph_edges[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

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

    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        cin >> score[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph_edges[u].push_back(v);
        graph_edges[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        bfs(i);
    }

    // 依次枚举 4 个互不相同的景点，再逐段检查 1 -> A -> B -> C -> D -> 1。
    ll answer = 0;
    for (int a = 2; a <= n; a++) {
        for (int b = 2; b <= n; b++) {
            for (int c = 2; c <= n; c++) {
                for (int d = 2; d <= n; d++) {
                    if (a == b || a == c || a == d || b == c || b == d || c == d) {
                        continue;
                    }
                    if (can_reach[1][a] && can_reach[a][b] && can_reach[b][c] &&
                        can_reach[c][d] && can_reach[d][1]) {
                        answer = max(answer, score[a] + score[b] + score[c] + score[d]);
                    }
                }
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

BFS 部分是 $O(n(n+m))$ ，枚举四个景点是 $O(n^4)$ ，总时间复杂度 $O(n^4+n(n+m))$ ，空间 $O(n^2)$ 。

瓶颈

当 $n=2500$ 时 $n^4$ 达到 $4\times10^{13}$ ，绝对跑不动。暴力里真正有价值的只有一件事：把“最多转车 $k$ 次”预处理成一个布尔可达矩阵。剩下的四重枚举必须消掉。

正解

思路

拆成“中间一段 + 两侧各选一个”

行程是

text

11 -> A -> B -> C -> D -> 1

如果固定中间的 $B\to C$ ，那么 $A$ 只需要满足 $1\to A\to B$ 都可达， $D$ 只需要满足 $C\to D\to 1$ 都可达，两边完全独立。

于是问题变成：对每个结点 $x$ ，维护“能排在 $x$ 前面的高分候选”集合

best[x]=\{\,p : p\neq x,\ can\_reach[1][p],\ can\_reach[p][x]\,\}.

因为图是无向的， $can\_reach$ 对称，所以 $best[C]$ 同时就是“能排在 $C$ 后面、且能回到家”的候选集合，两份候选列表可以共用同一套数据结构。

为什么只留 4 个候选

枚举一对 $B,C$ 后， $A$ 要避开 $\{B,C,D\}$ ， $D$ 要避开 $\{A,B,C\}$ 。设最优解是 $(A^\*,D^\*)$ ：

在 $best[B]$ 中，凡是排在 $A^\*$ 前面的候选，分数都不低于 $A^\*$ 。若它们都不是最优，就说明在配对 $(\cdot,D^\*)$ 下都被排除了，只能是等于 $B$ 、 $C$ 或 $D^\*$ ——最多 $3$ 个点。而 $B$ 本身已经不进候选表，所以真正会挤掉 $A^\*$ 的至多 $2$ 个点， $A^\*$ 最坏排在第 $3$ 位。

同理 $D^\*$ 最坏也排在第 $3$ 位。因此每份候选表保留前 $4$ 个就一定够用，枚举 $4\times4=16$ 组组合即可得到最优。

样例中的候选表

下面列出样例 $1$ 里每个结点的 best_node（括号内是分数），只保留分数最高的若干个。

$x$	$best[x]$ （按分数降序）
$2$	$3\,(7),\ 8\,(6)$
$3$	$2\,(9)$
$4$	$2\,(9),\ 3\,(7)$
$5$	$3\,(7),\ 7\,(3)$
$6$	$8\,(6),\ 7\,(3)$
$7$	$8\,(6)$
$8$	$2\,(9),\ 7\,(3)$

表中可以看出 $best[3]$ 只有一个候选 $2$ ，说明要经过 $3$ 就只能从 $2$ 过来。枚举到 $B=3,\ C=5$ 时， $A=2$ 、 $D$ 在 $best[5]=\{3,7\}$ 里排除掉与 $B=3$ 重合的 $3$ ，取 $7$ ，得到

s_2+s_3+s_5+s_7=9+7+8+3=27,

正是样例答案。

代码

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
116
117
118
119
120
121
122
123
124
125
126
127
128/**
 * 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-01 22:21
 * update_at: 2026-10-01 22:21
 */
// main.cpp：先从每个点 BFS 求限制步数内的可达性，再为每个点保留高分候选，最后枚举中间两个景点。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 2505;   // n <= 2500

int n, m, k;
ll score[MAXN];                // score[i]：景点 i 的分数，可达 1e18，必须用 ll
vector<int> graph_edges[MAXN]; // graph_edges[u]：与 u 有直达线路的点
bool can_reach[MAXN][MAXN];    // can_reach[x][y]：x 到 y 是否最多转车 k 次（即不超过 k+1 条边）
int best_node[MAXN][5];        // best_node[x][1..4]：能排在 x 前面的分数最高的 4 个候选景点
int dist[MAXN];                // BFS 距离数组，放全局避免大数组爆栈

// 从 start 出发做 BFS，把 k+1 条边以内可达的点都标记为 can_reach[start][y]。
void bfs(int start) {
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        dist[i] = -1;
    }
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        can_reach[start][u] = true;
        if (dist[u] == k + 1) {
            continue;   // 转车 k 次最多走 k+1 条边，不能再往外扩展
        }

        int cnt = graph_edges[u].size();
        for (int i = 0; i < cnt; i++) {
            int v = graph_edges[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

// 把 node 插入 best_node[x]，按分数从高到低维护前 4 个，重复的景点不再加入。
void add_candidate(int x, int node) {
    for (int i = 1; i <= 4; i++) {
        if (best_node[x][i] == node) {
            return;
        }
    }

    for (int i = 1; i <= 4; i++) {
        if (best_node[x][i] == 0 || score[node] > score[best_node[x][i]]) {
            for (int j = 4; j > i; j--) {
                best_node[x][j] = best_node[x][j - 1];
            }
            best_node[x][i] = node;
            return;
        }
    }
}

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

    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        cin >> score[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph_edges[u].push_back(v);
        graph_edges[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        bfs(i);
    }

    // best_node[x] 收的是“能排在 x 前面”的候选 a：满足 1 能到 a、a 能到 x。
    // 图是无向的，“x 后面”的候选条件形式相同，因此同一份列表可以两边复用。
    for (int x = 2; x <= n; x++) {
        for (int a = 2; a <= n; a++) {
            if (a != x && can_reach[1][a] && can_reach[a][x]) {
                add_candidate(x, a);
            }
        }
    }

    ll answer = 0;
    for (int b = 2; b <= n; b++) {
        for (int c = 2; c <= n; c++) {
            if (b == c || !can_reach[b][c]) {
                continue;
            }

            // b 的候选取 A、c 的候选取 D，凑出四个互不相同的景点。
            // 每份候选最多被 3 个点排除，所以保留前 4 个一定能取到最优。
            for (int i = 1; i <= 4; i++) {
                int a = best_node[b][i];
                if (a == 0 || a == b || a == c) {
                    continue;
                }
                for (int j = 1; j <= 4; j++) {
                    int d = best_node[c][j];
                    if (d == 0 || d == a || d == b || d == c) {
                        continue;
                    }
                    answer = max(answer, score[a] + score[b] + score[c] + score[d]);
                }
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n(n+m)+n^2\cdot 16)$ 。每个点做一次 BFS 共 $O(n(n+m))$ ，候选收集和枚举 $B,C$ 都是 $O(n^2)$ 级别，只带一个很小的常数。
空间复杂度： $O(n^2+n+m)$ ，主要来自可达矩阵。

总结

这题的关键拆法是不要直接枚举 $A,B,C,D$ ，而是先固定中间一段 $B\to C$ ：

BFS 把“最多转车 $k$ 次”变成布尔可达矩阵，负责判可行；
每个结点只留前 $4$ 个高分候选，把两侧选择从 $O(n)$ 降到常数。

“前 4 个够用”这件事来自一个很短的排除论证：一对 $B,C$ 固定后，一个候选最多被 $2$ 个点挤掉。这类“只留常数个最优候选”的剪枝是枚举题里把指数级压成多项式级的常用手法。

本文的 main.cpp 已用四重枚举的 brute.cpp 对拍 $600$ 组随机数据（含稠密图与稀疏图），两组题面样例均通过。

P8817 [CSP-S 2022] 假期计划

题目描述

小熊的地图上有 $n$ 个点，其中编号为 $1$ 的是它的家、编号为 $2, 3, \ldots, n$ 的都是景点。部分点对之间有双向直达的公交线路。如果点 $x$ 与 $z_1$ 、 $z_1$ 与 $z_2$ 、……、 $z_{k - 1}$ 与 $z_k$ 、 $z_k$ 与 $y$ 之间均有直达的线路，那么我们称 $x$ 与 $y$ 之间的行程可转车 $k$ 次通达；特别地，如果点 $x$ 与 $y$ 之间有直达的线路，则称可转车 $0$ 次通达。

很快就要放假了，小熊计划从家出发去 $4$ 个不同的景点游玩，完成 $5$ 段行程后回家：家 $\to$ 景点 A $\to$ 景点 B $\to$ 景点 C $\to$ 景点 D $\to$ 家且每段行程最多转车 $k$ 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A $\to$ 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D $\to$ 家这段行程转车时经过的点。

假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。

输入格式

第一行包含三个整数 $n, m, k$ ，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。

第二行包含 $n - 1$ 个正整数，分别表示编号为 $2, 3, \ldots, n$ 的景点的分数。

接下来 $m$ 行，每行包含两个正整数 $x, y$ ，表示点 $x$ 和 $y$ 之间有道路直接相连，保证 $1 \le x, y \le n$ ，且没有重边，自环。

输出格式

输出一个正整数，表示小熊经过的 $4$ 个不同景点的分数之和的最大值。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
108 8 1
9 7 1 8 2 3 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
8
9
10
117 9 0
1 1 1 2 3 4
1 2
2 3
3 4
1 5
1 6
1 7
5 4
6 4
7 4

输出 #2

text

说明/提示

【样例解释 #1】

当计划的行程为 $1 \to 2 \to 3 \to 5 \to 7 \to 1$ 时， $4$ 个景点的分数之和为 $9 + 7 + 8 + 3 = 27$ ，可以证明其为最大值。

行程 $1 \to 3 \to 5 \to 7 \to 8 \to 1$ 的景点分数之和为 $24$ 、行程 $1 \to 3 \to 2 \to 8 \to 7 \to 1$ 的景点分数之和为 $25$ 。它们都符合要求，但分数之和不是最大的。

行程 $1 \to 2 \to 3 \to 5 \to 8 \to 1$ 的景点分数之和为 $30$ ，但其中 $5 \to 8$ 至少需要转车 $2$ 次，因此不符合最多转车 $k = 1$ 次的要求。

行程 $1 \to 2 \to 3 \to 2 \to 3 \to 1$ 的景点分数之和为 $32$ ，但游玩的并非 $4$ 个不同的景点，因此也不符合要求。

【样例 #3】

见附件中的 holiday/holiday3.in 与 holiday/holiday3.ans。

【数据范围】

对于所有数据，保证 $5 \le n \le 2500$ ， $1 \le m \le 10000$ ， $0 \le k \le 100$ ，所有景点的分数 $1 \le s_i \le {10}^{18}$ 。保证至少存在一组符合要求的行程。

测试点编号	$n \le$	$m \le$	$k \le$
$1 \sim 3$	$10$	$20$	$0$
$4 \sim 5$	$10$	$20$	$5$
$6 \sim 8$	$20$	$50$	$100$
$9 \sim 11$	$300$	$1000$	$0$
$12 \sim 14$	$300$	$1000$	$100$
$15 \sim 17$	$2500$	$10000$	$0$
$18 \sim 20$	$2500$	$10000$	$100$

[CSP-S 2022] 假期计划

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

拆成“中间一段 + 两侧各选一个”

为什么只留 4 个候选

样例中的候选表

代码

复杂度

总结