在25世紀,人類文明遭受了一系列災難的破壞,這些災難最終導致人類建造了圍牆城市,為了便利運輸,由圍牆城市彼此用隧道相互連接。
每個有圍牆的城市都擁有一種特殊礦石,此礦石用來建造和維修包括隧道在內的所有基礎設施。
此特殊礦石與來自其他所有城市的其他礦石混合後,會形成一種幾乎堅不可摧的材料,稱為"Oreon"。
在圍牆的城市之外,有很多野蠻人,他們手持破壞性的武器,可以有效擊落任何航空運輸,和破壞隧道。
因此,每個城市都與一個以上的城市互連,以便當有其中一條互連隧道損壞時,還有另一條隧道可用。
如果隧道損壞則無法通行,將需要大量的"Oreon"來修復隧道。
當單個城市被孤立時(其所有互聯隧道都被破壞),則此城市無法製造"Oreon",最終將會導致城牆被破壞。
您作為國土防禦部的負責人,有責任確保所有城市在任何時候,至少通過一條互連的隧道保持通行。
面對防禦部隊中有限的人員,您必須確定使用最少人數的人來保護哪個隧道,並且不會讓任何城市被孤立。
輸入第一行包含一個整數T,代表有幾組測資。
每組測資第一行有一個數字N,N代表圍牆城市數量。
城市編號使用大寫英文字母順序編號。
接下來N行,代表城市隧道安全圖,數字代表需要的安全人員數量。
0代表不需要安全人員,也就表示在兩城市間沒有隧道。
每個數字由逗點和空白做分隔。
(安全圖中,第一行第2個數字代表城市A和城市B之間的隧道需要8位安全人員,以此類推)。
對於每組測資,輸出測資編號
接著輸出需要保護哪條隧道,以及該隧道保護人數。
請按隧道保護人數排列
如果人數相同,請按起始城市排列
如果起始城市相同,請按終點城市排列
(起始城市編號一定小於終點城市編號)
格式請參考範例輸出。
1 6 0, 8, 12, 0, 0, 7 8, 0, 0, 3, 0, 0 12, 0, 0, 0, 6, 0 0, 3, 0, 0, 0, 4 0, 0, 6, 0, 0, 5 7, 0, 0, 4, 5, 0
Case 1: B-D 3 D-F 4 E-F 5 C-E 6 A-F 7
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
30823 | kevin010411@ ... (傅詳閎) | e586 | 343 | 2022-06-14 15:17 |