[CSP-S 2022] 假期计划

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

先 BFS 求限制步数内可达，再为每个中间点保留高分候选并枚举中间两个景点。

OJ: luogu

题目 ID: P8817

难度:提高+/省选-

标签:图论BFS枚举贪心

日期: 2026-07-06 08:46

题意

从家 1 出发，依次游玩 4 个互不相同的景点 A,B,C,D，最后回到家。每一段行程都要求最多转车 $k$ 次，也就是最多走 $k+1$ 条边。

每个景点有分数，要求最大化：

text

1score[A] + score[B] + score[C] + score[D]

思路

小数据可以直接枚举 4 个景点，再检查 5 段路是否都能在限制内到达：

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// brute.cpp：小数据暴力解，枚举 4 个不同景点并检查 5 段行程是否可达。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, m, k;
long long score[MAXN];
vector<int> graph_edges[MAXN];
bool can_reach[MAXN][MAXN];

void bfs(int start) {
    int dist[MAXN];
    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();
        if (dist[u] > k + 1) {
            continue;
        }
        can_reach[start][u] = true;
        if (dist[u] == k + 1) {
            continue;
        }
        for (int i = 0; i < (int)graph_edges[u].size(); 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);
    }

    long long 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;
}

暴力枚举是 $O(n^4)$ ，当 $n=2500$ 时不可接受。但它提醒我们：真正需要判断的只是两点之间能否在 $k+1$ 条边内到达。

先从每个点做一次 BFS，得到 can_reach[x][y]，表示 $x$ 到 $y$ 是否满足单段行程限制。

路线是：

text

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

如果我们枚举中间两个景点 B,C，就只剩下两边要选：

A 需要满足 1 -> A 可达，并且 A -> B 可达；
D 需要满足 C -> D 可达，并且 D -> 1 可达。

图是无向图，所以“能作为某个点 $x$ 左侧景点的候选”与“能作为 $x$ 右侧景点的候选”条件形式相同：候选点 $p$ 需要满足 can_reach[1][p] 和 can_reach[p][x]。

于是可以对每个点 $x$ 预处理分数最高的前 4 个候选景点。为什么保留 4 个就够？枚举 B,C 时，一个候选最多会因为等于 A/B/C/D 中已有的点而不能用；我们只需要避开常数个点，保留前 4 个足够找到最优可用候选。

最后枚举所有有 can_reach[B][C] 的 B,C，在 best[B] 中选 A，在 best[C] 中选 D，检查四个景点互不相同并更新答案。

代码

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// main.cpp：BFS 预处理可达性，再枚举中间两个景点 B、C。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2505;

int n, m, k;
long long score[MAXN];
vector<int> graph_edges[MAXN];
bool can_reach[MAXN][MAXN];
int best_node[MAXN][4]; // best_node[x] 保存能作为 x 前一个景点的高分候选

void bfs(int start) {
    static int dist[MAXN];
    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();
        if (dist[u] > k + 1) {
            continue;
        }
        can_reach[start][u] = true;
        if (dist[u] == k + 1) {
            continue;
        }
        for (int i = 0; i < (int)graph_edges[u].size(); i++) {
            int v = graph_edges[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

void add_candidate(int x, int node) {
    for (int i = 0; i < 4; i++) {
        if (best_node[x][i] == node) {
            return;
        }
    }
    for (int i = 0; i < 4; i++) {
        if (best_node[x][i] == 0 || score[node] > score[best_node[x][i]]) {
            for (int j = 3; 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);
    }

    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);
            }
        }
    }

    long long answer = 0;
    for (int b = 2; b <= n; b++) {
        for (int c = 2; c <= n; c++) {
            if (b == c || !can_reach[b][c]) {
                continue;
            }
            for (int i = 0; i < 4; i++) {
                int a = best_node[b][i];
                if (a == 0 || a == b || a == c) {
                    continue;
                }
                for (int j = 0; 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;
}

复杂度

从每个点 BFS 一次，复杂度为 $O(n(n+m))$ 。预处理候选和枚举 B,C 都是 $O(n^2)$ 级别，只带一个很小的常数。

空间复杂度为 $O(n^2 + n + m)$ ，主要来自可达矩阵。

总结

本题的关键拆法是：不要直接枚举 A,B,C,D 四个景点，而是先固定中间连接 B -> C，再从两侧各取一个高分候选。

BFS 负责把“最多转车 $k$ 次”变成布尔可达矩阵；候选数组负责把两侧选择从 $O(n)$ 降到常数。

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] 假期计划

目录

题意

思路

代码

复杂度

总结