2022年CSP-J第二輪真題源碼解析個(gè)人解析，非評分標(biāo)準(zhǔn)答案T1[CSP-J?2022]假期計(jì)劃【題目描述】小熊的地圖上有n個(gè)點(diǎn)，其中編號為1的是它的家、編號2,3,....,n為的都是景點(diǎn)部分點(diǎn)對之間有雙向直達(dá)的公交線路如果點(diǎn)x與z1、z1?與?z2、……、zk - 1與?zk、zk?與?y?之間均有直達(dá)的線路，那么我們稱?x?與?y?之間的行程可轉(zhuǎn)車?k?次通達(dá)；特別地，如果點(diǎn)?x?與?y?之間有直達(dá)的線路，則稱可轉(zhuǎn)車?0?次通達(dá)很快就要放假了，小熊計(jì)劃從家出發(fā)去個(gè)不同的景點(diǎn)游玩，完成?5?段行程后回家：家→景點(diǎn) A?→景點(diǎn)B?→景點(diǎn)C?→景點(diǎn)D?→家且每段行程最多轉(zhuǎn)車?k?次轉(zhuǎn)車時(shí)經(jīng)過的點(diǎn)沒有任何限制，既可以是家、也可以是景點(diǎn)，還可以重復(fù)經(jīng)過相同的點(diǎn)例如，在景點(diǎn)A?→景點(diǎn)B 的這段行程中，轉(zhuǎn)車時(shí)經(jīng)過的點(diǎn)可以是家、也可以是景點(diǎn) C，還可以是景點(diǎn)D?→家這段行程轉(zhuǎn)車時(shí)經(jīng)過的點(diǎn)假設(shè)每個(gè)景點(diǎn)都有一個(gè)分?jǐn)?shù)，請幫小熊規(guī)劃一個(gè)行程，使得小熊訪問的四個(gè)不同景點(diǎn)的分?jǐn)?shù)之和最大輸入格式】第一行包含三個(gè)正整數(shù)?n, m, k，分別表示地圖上點(diǎn)的個(gè)數(shù)、雙向直達(dá)的點(diǎn)對數(shù)量、每段行程最多的轉(zhuǎn)車次數(shù)第二行包含?n -1個(gè)正整數(shù)，分別表示編號為?2, 3, …,n?的景點(diǎn)的分?jǐn)?shù)。

接下來?m行，每行包含兩個(gè)正整數(shù)?x, y，表示點(diǎn)?x和?y之間有道路直接相連，保證?1≤x,y≤n，且沒有重邊，自環(huán)輸出格式】輸出一個(gè)正整數(shù)，表示小熊經(jīng)過的?4不同景點(diǎn)的分?jǐn)?shù)之和的最大值輸入輸出樣例】輸入#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】當(dāng)計(jì)劃的行程為1→2→3→5→7→1?時(shí)，4個(gè)景點(diǎn)的分?jǐn)?shù)之和為?9+7+8+3=27，可以證明其為最大值行程?1→3→5→7→8→1?的景點(diǎn)分?jǐn)?shù)之和為?24、行程?1→3→2→8→7→1?的景點(diǎn)分?jǐn)?shù)之和為?25它們都符合要求，但分?jǐn)?shù)之和不是最大的行程?1→2→3→5→8→1?的景點(diǎn)分?jǐn)?shù)之和為?30，但其中?5→ 8?至少需要轉(zhuǎn)車?2?次，因此不符合最多轉(zhuǎn)車?k = 1?次的要求行程?1→2→3→2→3→1?的景點(diǎn)分?jǐn)?shù)之和為?32，但游玩的并非?4?個(gè)不同的景點(diǎn)，因此也不符合要求數(shù)據(jù)范圍】對于所有數(shù)據(jù)，保證 5≤n≤2500，1≤m≤10000，0≤k≤100，所有景點(diǎn)的分?jǐn)?shù) 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?<

step1，利用圖的bfs算法計(jì)算：從x（起點(diǎn)，1,2…,n）出發(fā)且轉(zhuǎn)車次數(shù)不超過k次的所有y（終點(diǎn)）這部分涉及到最短路徑問題，bfs求最短路徑的前提條件有兩個(gè)：無向圖；邊的權(quán)值為1（權(quán)值的累加和就是這個(gè)節(jié)點(diǎn)在這棵樹上的所在層次或者當(dāng)前深度）具體實(shí)現(xiàn)時(shí)將轉(zhuǎn)車次數(shù)k加1（因?yàn)閮牲c(diǎn)直達(dá)，轉(zhuǎn)車次數(shù)為0），將k作為bfs的結(jié)束條件（滿足條件：x能通過轉(zhuǎn)車次數(shù)不超過k次到達(dá)y，不滿足條件：x能到y(tǒng)但是轉(zhuǎn)車次數(shù)超過y；x沒有到y(tǒng)的路徑 ）step2，因?yàn)樾谐淌?→A→B→C→D→1，所以需要4個(gè)循環(huán)嵌套：[A：2→n；排除不滿足條件的A[B：2→n；排除不滿足條件的B [C：2→n；排除不滿足條件的C[D：2→n；排除不滿足條件的A,B,C,D；累加A,B,C,D的分?jǐn)?shù)并計(jì)算最大值；]//結(jié)束D循環(huán)]//結(jié)束C循環(huán)]//結(jié)束B循環(huán)]//結(jié)束A循環(huán)在上面的算法中，“排除不滿足條件的A”中的所指條件是：1能到A，“排除不滿足條件的B” 中的所指條件是：A能到B，“排除不滿足條件的C” 中的所指條件是：B能到C排除不滿足條件的A,B,C,D”中的條件與前面三個(gè)不同，其條件包含下面6種情況：1)C能到D；2)C能到1；3)A不能與C或D重合（A不可能與B重合，前面已經(jīng)判斷）；4)B不能與D重復(fù)（B不可能與A或C重合，前面已經(jīng)判斷）；5)C不能與A重復(fù)（C不可能與B或D重合，前面已經(jīng)判斷）；6)D不能與A或B重復(fù)（D不可能與C重合，前面已經(jīng)判斷）。

3)~6)的情況就是不需要判斷相鄰點(diǎn)，且在編程時(shí)只需考慮3)和6），因?yàn)?)和5)包含在3)和6)中，盡量減少多層循環(huán)中的最內(nèi)存選循環(huán)所包含的執(zhí)行代碼在編程中多個(gè)判斷條件的放置順序?qū)?zhí)行次數(shù)有一定的影響，少用else語句，配合continue，這樣邏輯上不容易混亂且執(zhí)行效率也不影響下面分析一下時(shí)間復(fù)雜度問題單個(gè)點(diǎn)的bfs時(shí)間復(fù)雜度為o(n)，因?yàn)殛?duì)列的最大長度是n，每一個(gè)點(diǎn)進(jìn)一次隊(duì)列出一次隊(duì)列；n個(gè)點(diǎn)的bfs時(shí)間復(fù)雜度為o(n2)，四重循環(huán)的時(shí)間復(fù)雜度為o(n4)，因此整個(gè)算法的時(shí)間復(fù)雜度為o(n4)，空間復(fù)雜度不存在問題，只需要注意將涉及到分?jǐn)?shù)計(jì)算的相關(guān)變量設(shè)置為long long int即可在程序中，用鄰接表來表示圖，在C++中可直接用元素是向量的一維數(shù)組來實(shí)現(xiàn)，用鄰接矩陣來存儲點(diǎn)與點(diǎn)之間的轉(zhuǎn)車次數(shù)，包括不能到達(dá)等情況（-1，0)，在C++中可直接用二維數(shù)組來實(shí)現(xiàn)運(yùn)行截圖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題目中已經(jīng)說明：保證至少存在一組符合要求的行程，因此自己設(shè)計(jì)測試用例的時(shí)候要考慮這個(gè)條件（k轉(zhuǎn)車次數(shù)可以為0，n≥5），最終的輸出結(jié)果一定不是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