e022: 4. 橋
Tags :
Accepted rate : 8人/10人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-01-23 13:15

Content

A區域和B區域被一條大河所分隔: A區域有M座城市(以1,2,…,M表示),而B區域有N座城市(以1,2,…,N表示)。為了方便兩區域城市之間的交通往來,政府興建了兩種橋樑用來連接A區域和B區域之間的城市:一種橋樑稱為「鋼筋混凝土橋」,是在混凝土中加入鋼筋做為原料,是一種經濟堅固的橋;另一種橋稱為「可動式橋」,是運河區常見的橋樑,為方便船隻通行以不同方式開啟橋面。在興建過程中必需滿足下列規則:

  1. 每座城市至少連接一座橋樑(鋼筋混凝土橋或可動式橋),鋼筋混凝土橋以數字1來表示,而可動式橋以數字0來表示。
  2. 任一座城市不可同時被兩座鋼筋混凝土橋所連接。
  3. 同一區域內的任兩座城市之間沒有橋樑連接。

當地政府為測試橋面的穩定度,希望工程師找出一條路徑從某一區域的城市開車出發經過一連串的橋樑到達另一區域的城市,同一座城市不能重覆經過,並依序分別經過可動式橋→鋼筋混凝土橋→可動式橋→鋼筋混凝土橋→…→鋼筋混凝土橋→可動式橋,需滿足下列特性:

  1. 所經過的橋樑種類,可動式橋和鋼筋混凝土橋需交互出現。
  2. 所經過的第一座橋和最後一座橋必需為可動式橋。
  3. 起點與終點城市自身無連接鋼筋混凝土橋。

我們稱滿足上述特性的路徑為擴增路徑,路徑的長度即為所經過的橋樑座數,最短為1(即只經一座可動式橋便到達終點城市),且已知最長的擴增路徑長度不超過L。本題請寫出一程式協助工程師找出最長擴增路徑的長度。如果找不到擴增路徑則輸出-1。

Input

每個子題內有數筆測資,對於每筆測資,第一行有4個數字,代表M值、N值、K值與L值,任兩個數字以空白隔開。第二行起接下來K行代表K座橋樑,每座橋樑對應三個數字(任兩個數字以空白隔開): 第一個數字代表在A區域的城市編號; 第二個數字代表在B區域的城市編號; 第三個數字代表橋樑為可動式橋或鋼筋混凝土橋。測試輸入以讀到檔案結尾為結束,一個輸入檔最多10筆測資。符合特性1與特性2的路徑數量不會超過5,000,000。

Output

針對所輸入的資料,輸出一個數字表示最長擴增路徑的長度。

Sample Input
2 2 3 20
1 1 0 
1 2 1
2 2 0
Sample Output
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (13%): 1.0s , <1M
公開 測資點#1 (21%): 1.0s , <1M
公開 測資點#2 (25%): 1.0s , <1M
公開 測資點#3 (41%): 1.0s , <1M
Hint :

本題有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。

Tags:
出處:
107學年度全國資訊學科能力競賽 [管理者:
icube (輸光光)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」