2022年CSP-J第二轮真题源码解析个人解析，非评分标准答案。T1CSP-J2022假期计划【题目描述】小熊的地图上有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. #include2. usingnamespacestd;3. typedeflonglongintll;4. intn,m,k;5. constintN=2505;6. intdNN;7. vectorGN;8. llscoreN;9. voidbfs(introot)10. for(inti=1;i=n;i+)drooti=-1;11. queueq;12. q.push(root),drootroot=0;13. while(q.size()14. intu=q.front();15. q.pop();16. if(drootu=k)break;17. for(intv:Gu)18. if(drootv=-1)drootv=drootu+1,q.push(v);19. 20. 21. 22. intmain()23. cinnmk;24. k+;25. for(inti=2;iscorei;27. 28. for(inti=1;ifirstNodesecondNode;31. GfirstNode.push_back(secondNode);32. GsecondNode.push_back(firstNode);33. 34. for(inti=1;i=n;i+)35. bfs(i);36. llmaxScore=0;37. for(intaIndex=2;aIndex=n;aIndex+)38. if(d1aIndex=-1)continue;39. for(intbIndex=2;bIndex=n;bIndex+)40. if(daIndexbIndex=-1)continue;41. if(bIndex=aIndex)continue;42. for(intcIndex=2;cIndex=n;cIndex+)43. if(dbIndexcIndex=-1)continue;44. if(cIndex=bIndex)continue;45. for(intdIndex=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. lltempTotalScore=scoreaIndex+scorebIndex+scorecIndex+scoredIndex;52. maxScore=max(maxScore,tempTotalScore);53. 54. 55. 56. 57. coutmaxScoreendl;58. return0;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. #include2. usingnamespacestd;3. typedeflonglongintll;4. constintN=2505;5. intn,m,k;6. llscoreN;7. vectorGN;8. intdNN;9. intbN3;10.11. voidbfs(introot)12. for(inti=1;i=n;i+)drooti=-1;13. queuei