A區域和B區域被一條大河所分隔: A區域有M座城市(以1,2,…,M表示)，而B區域有N座城市(以1,2,…,N表示)。為了方便兩區域城市之間的交通往來，政府興建了兩種橋樑用來連接A區域和B區域之間的城市：一種橋樑稱為「鋼筋混凝土橋」，是在混凝土中加入鋼筋做為原料，是一種經濟堅固的橋；另一種橋稱為「可動式橋」，是運河區常見的橋樑，為方便船隻通行以不同方式開啟橋面。在興建過程中必需滿足下列規則:
當地政府為測試橋面的穩定度，希望工程師找出一條路徑從某一區域的城市開車出發經過一連串的橋樑到達另一區域的城市，同一座城市不能重覆經過，並依序分別經過可動式橋→鋼筋混凝土橋→可動式橋→鋼筋混凝土橋→…→鋼筋混凝土橋→可動式橋，需滿足下列特性:
我們稱滿足上述特性的路徑為擴增路徑，路徑的長度即為所經過的橋樑座數，最短為1(即只經一座可動式橋便到達終點城市)，且已知最長的擴增路徑長度不超過L。本題請寫出一程式協助工程師找出最長擴增路徑的長度。如果找不到擴增路徑則輸出-1。
每個子題內有數筆測資，對於每筆測資，第一行有4個數字，代表M值、N值、K值與L值，任兩個數字以空白隔開。第二行起接下來K行代表K座橋樑，每座橋樑對應三個數字(任兩個數字以空白隔開): 第一個數字代表在A區域的城市編號; 第二個數字代表在B區域的城市編號; 第三個數字代表橋樑為可動式橋或鋼筋混凝土橋。測試輸入以讀到檔案結尾為結束，一個輸入檔最多10筆測資。符合特性1與特性2的路徑數量不會超過5,000,000。
針對所輸入的資料，輸出一個數字表示最長擴增路徑的長度。
2 2 3 20 1 1 0 1 2 1 2 2 0
3
本題有4個子題。
第一子題 （13分）
A區域的城市不超過10座；B區域的城市不超過10座；橋樑不超過100座，且已知最長的擴增路徑長度不超過20。
規格說明：
(1) 1 ≤ M ≤ 10
(2) 1 ≤ N ≤ 10
(3) 1 ≤ K ≤ 100
(4) L = 20
第二子題（21分）
輸入圖形是路徑。A區域的城市不超過100座；B區域的城市不超過100座；橋樑不超過10000座，且已知最長的擴增路徑長度不超過200。
規格說明：
(1) 1 ≤ M ≤ 100
(2) 1 ≤ N ≤ 100
(3) 1 ≤ K ≤ 10000
(4) L = 200。
第三子題（25分）
輸入圖形是樹形圖。A區域的城市不超過1000座；B區域的城市不超過1000座；橋樑不超過1000000座，且已知最長的擴增路徑長度不超過2000。
規格說明：
(1) 1 ≤ M ≤ 1000
(2) 1 ≤ N ≤ 1000
(3) 1 ≤ K ≤ 1000000
(4) L = 2000。
第四子題（41分）
A區域的城市不超過1000座；B區域的城市不超過1000座；橋樑不超過1000000座，且已知最長的擴增路徑長度不超過20。
規格說明：
(1) 1 ≤ M ≤ 1000
(2) 1 ≤ N ≤ 1000
(3) 1 ≤ K ≤ 1000000
(4) L = 20。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||