2022信奥赛C++提高组csp-s复赛真题及题解：假期计划

2022信奥赛C++提高组csp-s复赛真题及题解：假期计划

题目描述

小熊的地图上有n nn个点，其中编号为1 11的是它的家、编号为2 , 3 , … , n 2, 3, \ldots, n2,3,…,n的都是景点。部分点对之间有双向直达的公交线路。如果点x xx与z 1 z_1z1​、z 1 z_1z1​与z 2 z_2z2​、……、z k − 1 z_{k - 1}zk−1​与z k z_kzk​、z k z_kzk​与y yy之间均有直达的线路，那么我们称x xx与y yy之间的行程可转车k kk次通达；特别地，如果点x xx与y yy之间有直达的线路，则称可转车0 00次通达。

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

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

输入格式

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

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

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

输出格式

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

输入输出样例 1

输入 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

输出 1

27

输入输出样例 2

输入 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

输出 2

7

说明/提示

【样例解释 #1】

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

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

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

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

【数据范围】

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

思路分析

1. 图建模与距离预处理：

   • 使用邻接表存储无向图，通过BFS计算任意两点间的最短距离（边数）。
   • 由于n≤2500，对每个点做一次BFS，总复杂度O(n(n+m))。

2. 候选集预处理：

   • 对于每个景点b，找出所有可能的前驱a（满足1→a和a→b的距离均≤k+1），保留分数最大的3个。
   • 对于每个景点c，找出所有可能的后继d（满足c→d和d→1的距离均≤k+1），保留分数最大的3个。
   • 保留3个是为避免后续组合时因景点重复而失效。

3. 枚举与组合验证：

   • 枚举中间两个景点b和c（需满足b→c距离≤k+1）。
   • 对于每组(b,c)，枚举b的前驱a和c的后继d（最多9种组合），检查四个景点是否互不相同。
   • 计算分数和并更新最大值。

4. 时间复杂度：

   • BFS预处理：O(n(n+m)) ≈ 2500×12500 = 3.1×10⁷。
   • 候选集预处理：O(n²) ≈ 6.25×10⁶。
   • 枚举组合：O(n²×9) ≈ 2500×2500×9 = 5.6×10⁷。
   • 总复杂度在可接受范围内，能够通过所有测试点。

5. 正确性保证：

   • 所有行程要求（每段转车≤k次、景点不同）均被严格检查。
   • 通过预处理候选集和限制候选数量，在保证正确性的同时大幅降低枚举量。

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2505;constintINF=1e9;intn,m,k;ll s[N];// 景点分数，s[1]无用vector<int>g[N];// 邻接表intd[N][N];// 最短距离（边数）vector<int>pre[N];// pre[b]：b的可能前驱a（分数最大的3个）vector<int>suf[N];// suf[c]：c的可能后继d（分数最大的3个）// BFS求start到所有点的最短距离voidbfs(intstart){for(inti=1;i<=n;i++)d[start][i]=INF;d[start][start]=0;queue<int>q;q.push(start);while(!q.empty()){intu=q.front();q.pop();for(intv:g[u]){if(d[start][v]>d[start][u]+1){d[start][v]=d[start][u]+1;q.push(v);}}}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m>>k;for(inti=2;i<=n;i++)cin>>s[i];for(inti=0;i<m;i++){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}// 1. BFS预处理所有点对最短路for(inti=1;i<=n;i++)bfs(i);// 2. 预处理每个b的候选a（分数最大的3个）for(intb=2;b<=n;b++){vector<pair<ll,int>>tmp;// (分数, 景点编号)for(inta=2;a<=n;a++){if(a==b)continue;// 1->a 和 a->b 均需在k+1步内if(d[1][a]<=k+1&&d[a][b]<=k+1)tmp.emplace_back(s[a],a);}// 按分数降序排序，取前3个sort(tmp.begin(),tmp.end(),[](auto&x,auto&y){returnx.first>y.first;});for(inti=0;i<min(3,(int)tmp.size());i++)pre[b].push_back(tmp[i].second);}// 3. 预处理每个c的候选d（分数最大的3个）for(intc=2;c<=n;c++){vector<pair<ll,int>>tmp;for(intd_=2;d_<=n;d_++){if(d_==c)continue;// c->d 和 d->1 均需在k+1步内if(d[c][d_]<=k+1&&d[d_][1]<=k+1)tmp.emplace_back(s[d_],d_);}sort(tmp.begin(),tmp.end(),[](auto&x,auto&y){returnx.first>y.first;});for(inti=0;i<min(3,(int)tmp.size());i++)suf[c].push_back(tmp[i].second);}// 4. 枚举b和c，并组合a和dll ans=0;for(intb=2;b<=n;b++){for(intc=2;c<=n;c++){if(b==c||d[b][c]>k+1)continue;// 枚举候选a和d（最多3*3=9种组合）for(inta:pre[b]){for(intd_:suf[c]){// 确保四个景点互不相同if(a!=b&&a!=c&&a!=d_&&b!=c&&b!=d_&&c!=d_)ans=max(ans,s[a]+s[b]+s[c]+s[d_]);}}}}cout<<ans<<endl;return0;}

专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}