【正文】 60。 }39. }40. sum += T[m].length。41. e = T[m]。42. T[m] = T[k]。43. T[k] = e。44. v = T[k].endvex。45. for(j = k + 1。j n1。j ++){46. d= dist[v 1][T[j].endvex 1]。47. if(d T[j].length){48. T[j].length = d。49. T[j].fromvex = v。50. }51. }52. }53. printf(%d\n,sum)。54. }55. int main(){56. int n,m,i,j。57. int from,end,value。58. while(scanf(%d %d,amp。n,amp。m) != EOF){59. memset(visited,0,M * sizeof(int))。60. if(n == 0) return 0。61. for(i = 0。i M。i ++){62. for(j = 0。j M。j ++){63. arcs[i][j] = 0。64. dist[i][j] = MAX。65. }66. }67. for(i = 0。i n。i ++){68. scanf(%d%d%d,amp。from,amp。end,amp。value)。69. dist[from 1][end 1] = value。70. dist[end 1][from 1] = value。71. arcs[from][end] = 1。72. arcs[end][from] = 1。73. }74. DFS(1,m)。75. for(i = 1。i = m。i ++){76. if(visited[i] == 0){77. printf(?\n)。78. break。79. }80. }81. if(i m){82. prim(m)。83. }84. }85. return 0。86. }六、 最大報銷額題目描述： 現(xiàn)有一筆經(jīng)費可以報銷一定額度的發(fā)票。允許報銷的發(fā)票類型包括買圖書（A類）、文具（B類）、差旅（C類），要求每張發(fā)票的總額不得超過1000元，每張發(fā)票上，單項物品的價值不得超過600元?，F(xiàn)請你編寫程序，在給出的一堆發(fā)票中找出可以報銷的、不超過給定額度的最大報銷額。輸入： 測試輸入包含若干測試用例。每個測試用例的第1行包含兩個正數(shù) Q 和 N，其中 Q 是給定的報銷額度，N（N=30）是發(fā)票張數(shù)。隨后是 N 行輸入，每行的格式為： m Type_1:price_1 Type_2:price_2 ... Type_m:price_m 其中正整數(shù) m 是這張發(fā)票上所開物品的件數(shù)，Type_i 和 price_i 是第 i 項物品的種類和價值。物品種類用一個大寫英文字母表示。當N為0時，全部輸入結(jié)束，相應的結(jié)果不要輸出。輸出： 對每個測試用例輸出1行，即可以報銷的最大數(shù)額，精確到小數(shù)點后2位。樣例輸入： 32 A: B:1 C:3 A: A: X: 22 B: A:1 C: 32 B: A:1 C:1 A: 0樣例輸出： 答案：AC代碼, 基本思路是遞歸求解 1. includeiostream2. include3. include4. includeiomanip5. include6.7. using namespace std。8.9. double a[31]。10. int top。11.12. double max(double x,double y){13. if(xy)return x。14. else return y。15. }16.17. double maxvalue(int k,double left,double Q){//遞歸求最大報銷額 18. //coutleft=left Q=Qendl。19. int mark=0。20. double t=0。21. for(int i=k。itop。i++)22. if(a[i]=left){23. t=max(maxvalue(i+1,lefta[i],Q),t)。24. //coutt=tendl。25. mark=1。26. }27. if(mark==0)return Qleft。28. else return t。29. } 30.31. int main(void){32. double Q,sum,value,total。33. int n,m,mark。34. char c,d。35. while(scanf(%lf%d,amp。Q,amp。n)!=EOF){36. if(n==0)break。37. top=0。38. for(int i=0。in。i++){39. scanf(%d,amp。m)。40. mark=1。41. sum=0。42. for(int j=0。jm。j++){43. scanf( %c:%lf,amp。c,amp。value)。44. //coutc=c value=valueendl。45. if(value||c39。A39。=3)mark=0。46. sum=sum+value。47. }48. if(mark==1amp。amp。sum=){49. a[top]=sum。50. //couttop=top a[top]=a[top]endl。51. top++。52. }53. }54. printf(%.*lf\n,2,maxvalue(0,Q,Q))。55. }56. return 0。57. }歡迎您的光臨，！希望您提出您寶貴的意見，你的意見是我進步的動力。贈語； 如果我們做與不做都會有人笑，如果做不好與做得好還會有人笑，那么我們索性就做得更好，來給人笑吧！ 現(xiàn)在你不玩命的學，以后命玩你。我不知道年少輕狂，我只知道勝者為王。不要做金錢、權(quán)利的奴隸；應學會做“金錢、權(quán)利”的主人。什么時候離光明最近？那就是你覺得黑暗太黑的時候。最值得欣賞的風景，是自己奮斗的足跡。壓力不是有人比你努力，而是那些比你牛幾倍的人依然比你努力。學習參考