2022年CSP-S第二轮C++真题源码解析1
2022年CSP-J第二轮真题源码解析个人解析，非评分标准答案。T1CSP-J 2022假期计划【题目描述】小熊的地图上有n个点，其中编号为1的是它的家、编号2,3,.,n为的都是景点。部分点对之间有双向直达的公交线路。如果点x与z1、z1 与 z2、zk - 1与 zk、zk 与 y 之间均有直达的线路，那么我们称 x 与 y 之间的行程可转车 k 次通达；特别地，如果点 x 与 y 之间有直达的线路，则称可转车 0 次通达。很快就要放假了，小熊计划从家出发去个不同的景点游玩，完成 5 段行程后回家：家景点 A 景点B 景点C 景点D 家且每段行程最多转车 k 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点A 景点B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点D 家这段行程转车时经过的点。假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。【输入格式】第一行包含三个正整数 n, m, k，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。第二行包含 n -1个正整数，分别表示编号为 2, 3, ,n 的景点的分数。接下来 m行，每行包含两个正整数 x, y，表示点 x和 y之间有道路直接相连，保证 1x,yn，且没有重边，自环。【输出格式】输出一个正整数，表示小熊经过的 4不同景点的分数之和的最大值。【输入输出样例】输入#18 8 19 7 1 8 2 3 61 22 33 44 55 66 77 88 1输出#127输入#27 9 01 1 1 2 3 41 22 33 41 51 61 75 46 47 4输出#27【样例解释#1】当计划的行程为123571 时，4个景点的分数之和为 9+7+8+3=27，可以证明其为最大值。行程 135781 的景点分数之和为 24、行程 132871 的景点分数之和为 25。它们都符合要求，但分数之和不是最大的。行程 123581 的景点分数之和为 30，但其中 5 8 至少需要转车 2 次，因此不符合最多转车 k = 1 次的要求。行程 123231 的景点分数之和为 32，但游玩的并非 4 个不同的景点，因此也不符合要求。【数据范围】对于所有数据，保证 5n2500，1m10000，0k100，所有景点的分数 1si1018。保证至少存在一组符合要求的行程。参考源码1：1. #include <bits/stdc+.h>2. using namespace std;3. typedef long long int ll;4. int n, m, k;5. const int N = 2505;6. int dNN;7. vector<int> GN;8. ll scoreN;9. void bfs(int root) 10. for (int i = 1; i <= n; i+) drooti = -1;11. queue<int> q;12. q.push(root), drootroot = 0;13. while (q.size() 14. int u = q.front();15. q.pop();16. if (drootu = k) break;17. for (int v : Gu) 18. if (drootv = -1) drootv = drootu + 1, q.push(v);19. 20. 21. 22. int main() 23. cin >> n >> m >> k;24. k+;25. for (int i = 2; i <= n; i+) 26. cin >> scorei;27. 28. for(int i=1;i<=m;i+)29. int firstNode, secondNode;30. cin >> firstNode >> secondNode;31. GfirstNode.push_back(secondNode);32. GsecondNode.push_back(firstNode);33. 34. for (int i = 1; i <= n; i+)35. bfs(i);36. ll maxScore = 0;37. for (int aIndex = 2; aIndex <= n; aIndex+) 38. if (d1aIndex = -1) continue;39. for (int bIndex = 2; bIndex <= n; bIndex+) 40. if (daIndexbIndex = -1) continue;41. if (bIndex = aIndex) continue;42. for (int cIndex = 2; cIndex <= n; cIndex+) 43. if (dbIndexcIndex = -1) continue;44. if (cIndex = bIndex) continue;45. for (int dIndex = 2; dIndex <= n; dIndex+) 46. if (dcIndexdIndex = -1) continue;47. if (dIndex = cIndex) continue;48. if (d1dIndex = -1) continue;49. if (aIndex = cIndex) | (aIndex = dIndex) continue;50. if (dIndex = aIndex) | (dIndex = bIndex) continue;51. ll tempTotalScore = scoreaIndex + scorebIndex + scorecIndex + scoredIndex;52. maxScore = max(maxScore, tempTotalScore);53. 54. 55. 56. 57. cout << maxScore << endl;58. return 0;59. 算法思路1：纯暴力算法，但是不可能获得100分，在1520的测试点上可能TLE。step1，利用图的bfs算法计算：从x（起点，1,2,n）出发且转车次数不超过k次的所有y（终点）。这部分涉及到最短路径问题，bfs求最短路径的前提条件有两个：无向图；边的权值为1（权值的累加和就是这个节点在这棵树上的所在层次或者当前深度）。具体实现时将转车次数k加1（因为两点直达，转车次数为0），将k作为bfs的结束条件（满足条件：x能通过转车次数不超过k次到达y，不满足条件：x能到y但是转车次数超过y；x没有到y的路径 ）。step2，因为行程是1ABCD1，所以需要4个循环嵌套：A：2n；排除不满足条件的AB：2n；排除不满足条件的B C：2n；排除不满足条件的CD：2n；排除不满足条件的A,B,C,D；累加A,B,C,D的分数并计算最大值；/结束D循环/结束C循环/结束B循环/结束A循环在上面的算法中，“排除不满足条件的A”中的所指条件是：1能到A，“排除不满足条件的B” 中的所指条件是：A能到B，“排除不满足条件的C” 中的所指条件是：B能到C。“排除不满足条件的A,B,C,D”中的条件与前面三个不同，其条件包含下面6种情况：1)C能到D；2)C能到1；3)A不能与C或D重合（A不可能与B重合，前面已经判断）；4)B不能与D重复（B不可能与A或C重合，前面已经判断）；5)C不能与A重复（C不可能与B或D重合，前面已经判断）；6)D不能与A或B重复（D不可能与C重合，前面已经判断）。3)6)的情况就是不需要判断相邻点，且在编程时只需考虑3)和6），因为4)和5)包含在3)和6)中，尽量减少多层循环中的最内存选循环所包含的执行代码。在编程中多个判断条件的放置顺序对执行次数有一定的影响，少用else语句，配合continue，这样逻辑上不容易混乱且执行效率也不影响。下面分析一下时间复杂度问题。单个点的bfs时间复杂度为o(n)，因为队列的最大长度是n，每一个点进一次队列出一次队列；n个点的bfs时间复杂度为o(n2)，四重循环的时间复杂度为o(n4)，因此整个算法的时间复杂度为o(n4)，空间复杂度不存在问题，只需要注意将涉及到分数计算的相关变量设置为long long int即可。在程序中，用邻接表来表示图，在C+中可直接用元素是向量的一维数组来实现，用邻接矩阵来存储点与点之间的转车次数，包括不能到达等情况（-1，0)，在C+中可直接用二维数组来实现。运行截图1：测试用例1测试用例2测试用例3测试用例4测试用例51ACDB1，1+3+4+2=101BDCA1，2+4+3+1=10题目中已经说明：保证至少存在一组符合要求的行程，因此自己设计测试用例的时候要考虑这个条件（k转车次数可以为0，n5），最终的输出结果一定不是0。参考源码2：1. #include <bits/stdc+.h>2. using namespace std;3. typedef long long int ll;4. const int N = 2505;5. int n, m, k;6. ll scoreN;7. vector<int> GN;8. int dNN;9. int bN3;10.11. void bfs(int root) 12. for (int i = 1; i <= n; i+) drooti = -1;13. queue<i
