企业官网建设流程全解析

继续刷 CSP-S 2022 真题。这题考点是广度优先搜索，先把题意吃透。

题目来源：ACGO A50000 ｜ 洛谷 P8817
难度定位：提高+/省选- ｜ 通过率：40.39%

一、题目信息

题目名称：假期计划

所属赛事：2022 年 CSP-S 组复赛

官方难度：提高+/省选-

涉及知识点：广度优先搜索

题目链接：https://www.acgo.cn/problemset/info/50000

洛谷编号：P8817（同一道题，两个平台均可提交，代码通用）

坑点（无数人 WA 的核心）

• 记得标记已访问，否则会死循环或重复计数
• 递归深度大时考虑改成显式栈或迭代写法
• 高难度题的暴力分很关键，先写一版能过的部分分再想正解

题意简述

先把题目翻译成人话：

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

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

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

前置知识

在动笔之前，把这题用到的知识铺垫一下，不熟悉的跟着看。

一条路走到黑再回头

DFS 适合枚举所有方案，BFS 适合求最少步数。搜索题一定要先想清楚剪枝，否则指数级复杂度会超时。

二、思路分析

CSP-S 2022 中难度为提高+/省选-，中场，先拿暴力分是合理的选择。

来推一下这题该怎么做。

这道「假期计划」属于搜索类问题。拿不到官方题解的题，我们把推导过程还原一遍，重点是让你能自己想出来。

第一步，读清目标。题目要我们求什么？是求一个数值、一个方案，还是判断可行性？目标不同，做法差别很大。

第二步，看数据范围。数据范围往往直接告诉你该用什么复杂度的算法，这一步比想算法更重要。

第三步，从小规模入手。先手算题目给的样例，把中间过程写下来，规律往往就在这个过程中浮现。

第四步，落到搜索的标准套路。确定方向后，把题目条件翻译成代码结构，再处理边界。

下面给出的是一份可在 ACGO 与洛谷两平台提交的参考实现，建议先自己写一遍，再回来对照。

三、完整代码

#include <cstdio> #include <vector> #include <queue> #include <algorithm> #include <cstring> using namespace std; // CSP-S 2022 假期计划 // n 个点，1 号为家，2..n 为景点，每个景点有权值 a[i]。边为双向直达线路。 // 「x 到 y 可转车 k 次通达」= 存在长度 <= k+1（边数）的路径。 // 求选 4 个互不相同的景点 A,B,C,D，使 家→A→B→C→D→家 每段都可转车 k 次通达， // 且四个景点权值之和最大，输出该最大值（若不存在合法方案输出 0）。 // // 思路： // ① 对每个点做一次「限制深度 = k+1」的 BFS，得到可达点集合。 // 由于 k 很小（本题 k <= 100，但点数大时 BFS 深度受限）， // 更稳的通用做法是对每个点 BFS 到深度 k+1。 // ② 把「可达」关系当作有向图 G：u→v 当且仅当 v 可从 u 在 <=k+1 步内到达。 // ③ 枚举中间两点 B,C，则 A 必须是 1 可达、且 A→B 可达、A 与 B,C,D 不同； // D 必须是 1 可达、且 C→D 可达、D 与 A,B,C 不同。 // 于是对每个点 B 预处理「从 1 可达且能到 B 的点」中权值最大的前 3 个 // （保存 (值, 编号)），对每个点 C 同理预处理「从 C 可达且能到 1 的点」的前 3 个。 // 然后枚举 B、C 与各自前 3 候选的组合（3×3），判重后取最大和。 // ④ 这样避免了两两重复，复杂度为 BFS 的 O(n(n+m)) 与枚举的 O(n * 9)。 // // 说明：为通用起见，本文用「对每点 BFS 限制深度」的实现；当 k+1 较大时复杂度会上升， // 但正确性有保证，适合作为教学与样例验证代码。 const int MAXN = 2505; const int MAXM = 20005; int n, m, k; long long a[MAXN]; vector<int> adj[MAXN]; // good[i][j] : i 到 j 是否可在 <= k+1 步内到达 static bool good[MAXN][MAXN]; // BFS 从 s 出发，深度限制 lim，标记可达 static int distArr[MAXN]; void bfs(int s, int lim) { for (int i = 1; i <= n; ++i) distArr[i] = -1; queue<int> q; distArr[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); if (distArr[u] == lim) continue; for (size_t t = 0; t < adj[u].size(); ++t) { int v = adj[u][t]; if (distArr[v] == -1) { distArr[v] = distArr[u] + 1; q.push(v); } } } for (int v = 1; v <= n; ++v) good[s][v] = (distArr[v] != -1); } int main() { scanf("%d %d %d", &n, &m, &k); for (int i = 2; i <= n; ++i) scanf("%lld", &a[i]); a[1] = 0; for (int i = 0; i < m; ++i) { int u, v; scanf("%d %d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } int lim = k + 1; for (int s = 1; s <= n; ++s) bfs(s, lim); // preA[b] : (权值, 编号) 前 3 —— 满足 good[1][x] && good[x][b]，x != 1 // preD[c] : 满足 good[c][x] && good[x][1]，x != 1 static pair<long long, int> preA[MAXN][3]; static pair<long long, int> preD[MAXN][3]; for (int b = 1; b <= n; ++b) for (int t = 0; t < 3; ++t) preA[b][t] = make_pair(-1, 0); for (int c = 1; c <= n; ++c) for (int t = 0; t < 3; ++t) preD[c][t] = make_pair(-1, 0); for (int x = 2; x <= n; ++x) { if (!good[1][x]) continue; for (int b = 2; b <= n; ++b) { if (b == x) continue; if (good[x][b]) { // 插入 preA[b] pair<long long, int> cand(a[x], x); for (int t = 0; t < 3; ++t) { if (cand.first > preA[b][t].first) { for (int s = 2; s > t; --s) preA[b][s] = preA[b][s - 1]; preA[b][t] = cand; break; } } } } } for (int x = 2; x <= n; ++x) { if (!good[x][1]) continue; for (int c = 2; c <= n; ++c) { if (c == x) continue; if (good[c][x]) { pair<long long, int> cand(a[x], x); for (int t = 0; t < 3; ++t) { if (cand.first > preD[c][t].first) { for (int s = 2; s > t; --s) preD[c][s] = preD[c][s - 1]; preD[c][t] = cand; break; } } } } } long long ans = 0; for (int b = 2; b <= n; ++b) { // b 只需「可由 A 到达」，不要求家直接可达 for (int c = 2; c <= n; ++c) { if (c == b) continue; if (!good[b][c]) continue; // B 能到 C // 注意：回家的是 D，不是 C；C→家的可达性由 preD 的构造保证。 for (int i = 0; i < 3; ++i) { if (preA[b][i].second == 0) continue; int A = preA[b][i].second; if (A == b || A == c) continue; for (int j = 0; j < 3; ++j) { if (preD[c][j].second == 0) continue; int D = preD[c][j].second; if (D == b || D == c || D == A) continue; long long sum = a[A] + a[b] + a[c] + a[D]; if (sum > ans) ans = sum; } } } } printf("%lld\n", ans); return 0; }

四、代码分段拆解

把代码拆成几块来看，逐块理解比整体啃更容易。

头文件与全局变量

先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用，好处是函数之间共享方便，代价是要小心初始化和被意外改写。

#include <cstdio> #include <vector> #include <queue> #include <algorithm> #include <cstring>

using namespace std; const int MAXN = 2505; const int MAXM = 20005; int n, m, k; long long a[MAXN]; vector<int> adj[MAXN]; int u = q.front(); q.pop(); int v = adj[u][t]; int main() { int u, v; scanf("%d %d", &u, &v); int lim = k + 1;

主体逻辑

主体部分按顺序完成读入、计算、输出。main函数尽量保持线性，把复杂的逻辑拆成独立函数，出问题时更容易定位。

图的遍历

遍历时记录访问状态，避免重复访问或死循环。递归深度大时要留意栈空间。

五、实例模拟

拿真实样例跑一遍，看看逻辑对不对得上。

样例 1

输入：

8 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

输出：

27

样例 2

输入：

7 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

输出：

7

以第一组样例为例，输入是8 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，正确输出是27。建议把这两行数据抄在纸上，用上面的代码手动走一遍，重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西，比看懂代码印象深得多。

六、踩坑总结

复盘一下，这些点记住下次能省很多调试时间。

1. 记得标记已访问，否则会死循环或重复计数
2. 递归深度大时考虑改成显式栈或迭代写法
3. 高难度题的暴力分很关键，先写一版能过的部分分再想正解

另外提醒一句：这题在 CSP-S 2022 里是提高+/省选-难度，考场上如果没有把握拿满分，先把暴力写法交上去拿到部分分，再回头优化。CSP 是打分制，空着不写才是最亏的。

七、知识点拓展

这题的核心是搜索。

搜索题的关键永远是剪枝。写完暴力后统计一下状态数，如果远超时限，就想办法在不影响正确性的前提下砍掉分支。

建议的练习路径：

1. 先把本题独立写一遍，不看代码，遇到卡壳再看提示
2. 换个平台提交（ACGO 和洛谷都试试），确保代码在两个平台都能过
3. 找两到三道同类型的题练手，巩固这类问题的识别能力

八、适用人群

如果你是下面这几种情况，这题值得动手写一遍：

• 目标是 CSP-S 高分或省选的同学
• 想通过真题理解高难度题如何从暴力优化到正解的同学
• 想弄明白搜索类问题标准解法的同学

如果这篇对你有帮助，点个赞让更多备考的同学看到。

关于这个系列

这是「CSP 真题逐题精讲」的第 34 篇。我会按年份从 2019 一路刷到 2025，
CSP-J 和 CSP-S 全覆盖。每篇都给：双平台题号（ACGO + 洛谷）+ 逐行代码拆解 + 真实样例模拟。

跟着刷完这一套，CSP 第一轮的选择题和基础题基本就稳了。

下一篇：CSP-J 2023 小苹果（普及-）

👉 关注我，不错过后续更新。评论区告诉我你现在刷到哪一年了，我看看能不能按大家的进度调整更新节奏。