2022年CSP-S第二轮C++真题源码解析1.docx

2022年CSP-J第二轮真题源码解析个人解析，非评分标准答案T1[CSP-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之间有道路直接相连，保证 1≤x,y≤n，且没有重边，自环输出格式】输出一个正整数，表示小熊经过的 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】当计划的行程为1→2→3→5→7→1 时，4个景点的分数之和为 9+7+8+3=27，可以证明其为最大值行程 1→3→5→7→8→1 的景点分数之和为 24、行程 1→3→2→8→7→1 的景点分数之和为 25它们都符合要求，但分数之和不是最大的行程 1→2→3→5→8→1 的景点分数之和为 30，但其中 5→ 8 至少需要转车 2 次，因此不符合最多转车 k = 1 次的要求行程 1→2→3→2→3→1 的景点分数之和为 32，但游玩的并非 4 个不同的景点，因此也不符合要求数据范围】对于所有数据，保证 5≤n≤2500，1≤m≤10000，0≤k≤100，所有景点的分数 1≤si≤1018。

保证至少存在一组符合要求的行程参考源码1：1. #include 2. using namespace std;3. typedef long long int ll;4. int n, m, k;5. const int N = 2505;6. int d[N][N];7. vector G[N];8. ll score[N];9. void bfs(int root) {10.     for (int i = 1; i <= n; i++) d[root][i] = -1;11.     queue q;12.     q.push(root), d[root][root] = 0;13.     while (q.size()) {14.         int u = q.front();15.         q.pop();16.         if (d[root][u] == k) break;17.         for (int v : G[u]) {18.             if (d[root][v] == -1) d[root][v] = d[root][u] + 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 >> score[i];27.     }28.     for(int i=1;i<=m;i++){29.         int firstNode, secondNode;30.         cin >> firstNode >> secondNode;31.         G[firstNode].push_back(secondNode);32.         G[secondNode].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 (d[1][aIndex] == -1) continue;39.         for (int bIndex = 2; bIndex <= n; bIndex++) {40.             if (d[aIndex][bIndex] == -1) continue;41.             if (bIndex == aIndex) continue;42.             for (int cIndex = 2; cIndex <= n; cIndex++) {43.                 if (d[bIndex][cIndex] == -1) continue;44.                 if (cIndex == bIndex) continue;45.                 for (int dIndex = 2; dIndex <= n; dIndex++) {46.                     if (d[cIndex][dIndex] == -1) continue;47.                     if (dIndex == cIndex) continue;48.                     if (d[1][dIndex] == -1) continue;49.                     if ((aIndex == cIndex) || (aIndex == dIndex)) continue;50.                     if ((dIndex == aIndex) || (dIndex == bIndex)) continue;51.                     ll tempTotalScore = score[aIndex] + score[bIndex] + score[cIndex] + score[dIndex];52.                     maxScore = max(maxScore, tempTotalScore);53.                 }54.             }55.         }56.     }57.     cout << maxScore << endl;58.     return 0;59. }算法思路1：纯暴力算法，但是不可能获得100分，在15~20的测试点上可能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，因为行程是1→A→B→C→D→1，所以需要4个循环嵌套：[A：2→n；排除不满足条件的A[B：2→n；排除不满足条件的B [C：2→n；排除不满足条件的C[D：2→n；排除不满足条件的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测试用例51→A→C→D→B→1，1+3+4+2=101→B→D→C→A→1，2+4+3+1=10题目中已经说明：保证至少存在一组符合要求的行程，因此自己设计测试用例的时候要考虑这个条件（k转车次数可以为0，n≥5），最终的输出结果一定不是0。

参考源码2：1. #include 2. using namespace std;3. typedef long long int ll;4. const int N = 2505;5. int n, m, k;6. ll score[N];7. vector G[N];8. int d[N][N];9. int b[N][3];10.11. void bfs(int root) {12.     for (int i = 1; i <= n; i++) d[root][i] = -1;13.     queue