圖論練習題(3)

1、圖論練習題（3）題1、士兵排隊（soldier.pas）:8000/vijos/Problem_Show.asp?id=1478問題描述：A B D F 有n個士兵（1n26），編號依次為A、B、C， 隊列訓練時，指揮官要把一些士兵從高到矮依次排成一行。但現(xiàn)在指揮官不能直接獲得每個人的身高信息，只能獲得“p1比p2高”這樣的比較結(jié)果（p1，p2'A'，'Z'），記為p1>p2。例如A>B，B>D，F(xiàn)>D。士兵的身高關(guān)系如圖所示： 對應的排隊方案有三個：AFBD、FABD、ABFD。輸入：（soldier.in）第一行：一個整數(shù)k第二至第k

2、+1行：每行兩個大寫字母（中間和末尾都沒有空格），代表兩個士兵，且第一個士兵高度大于第二個士兵。輸出：（soldier.out）一個只包含大寫字母的字符序列，表示排隊方案（只要一種方案即可）。輸入樣例：（soldier.in）3ABBDFD輸出樣例：（soldier.out）AFBD題2、生產(chǎn)資料（ziliao.pas）:8000/vijos/Problem_Show.asp?id=1477問題描述某工廠發(fā)現(xiàn)廠里的機器在生產(chǎn)產(chǎn)品時需要消耗大量的原材料,現(xiàn)在廠里想找出消耗原材料最大的一條生產(chǎn)線路加以改進以降低成本。已知廠里的生產(chǎn)線路是一個有向的無環(huán)網(wǎng)絡，有n個機器分別代表網(wǎng)絡中的n 個結(jié)點，弧i

3、，j（ij表示原材料從機器i傳到機器j的損耗數(shù)量。輸入格式輸入文件：第一行兩個整數(shù)n，m（n=100，m=100分別表示網(wǎng)絡中的結(jié)點的個數(shù)與弧數(shù)，第二行至m+1行，每行三個整數(shù)a,b,c，表示弧a,b的損耗為c。輸出格式輸出文件：只一個整數(shù)，損耗最大線路的損耗量。輸入樣例8 1212 61 3 72 4 32 5 53 5 44 6 24 8 55 4 35 6 45 7 36 8 27 8 4輸出樣例：19題3、課程安排問題 (topo.pas/c/cpp)問題描述一個軟件專業(yè)的學生必須學習一系列基本課程，其中有些課程是基礎課，它獨立于其它課程，如高等數(shù)學、計算引論；而另一些課程必須在學完作

4、為它的基礎的先修課程才能開始。如，在程序設計基礎和離散數(shù)學學完之前就不能開始學習數(shù)據(jù)結(jié)構(gòu)。這些先決條件定義了課程之間的領先（優(yōu)先）關(guān)系。請你在符合上述領先（優(yōu)先）條件的前提下，給出所有課程的一個有序序列，以方便學校排課。【輸入格式】輸入文件有若干行第一行，一個整數(shù)n，表示共有n(0<n<=100)門課程第2-n+1行分別表示第1-n門課程的先修課程信息，每行有若干個整數(shù)m,s1,s2,.,smm表示該門課程有m門先修課程，s1,s2,.,sm分別表示m門先修課的編號，如果該門課沒有先修課程，則m為0。【輸出格式】一行，n個整數(shù)，表示n門課程編號的有序序列(如果這樣的序列不存在，則輸出no)4 0 1 1 1 1 2 2 31 2 3 4 題4、數(shù)列問題 （topoa.pas/c/cpp） 【問題描述】尋找一個由n個整數(shù)組成的數(shù)列，其中任意連續(xù)p個整數(shù)之和為正，任意連續(xù)q個整數(shù)之和為負。若不存在這樣的整數(shù)數(shù)列，則輸出no，否則輸出其中一個數(shù)列?！据斎敫袷健枯斎胛募挥幸恍?，三個整數(shù)n,p,q(0<n<=100，q<n，p<n，p<>q)【輸出格式】一行，n個整數(shù)，表示滿足條件的序列，每