e586. 01208 - Oreon
Tags :
Accepted rate : 47人/50人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-05-27 13:53

Content

在25世紀,人類文明遭受了一系列災難的破壞,這些災難最終導致人類建造了圍牆城市,為了便利運輸,由圍牆城市彼此用隧道相互連接。
每個有圍牆的城市都擁有一種特殊礦石,此礦石用來建造和維修包括隧道在內的所有基礎設施。
此特殊礦石與來自其他所有城市的其他礦石混合後,會形成一種幾乎堅不可摧的材料,稱為"Oreon"。
在圍牆的城市之外,有很多野蠻人,他們手持破壞性的武器,可以有效擊落任何航空運輸,和破壞隧道。
因此,每個城市都與一個以上的城市互連,以便當有其中一條互連隧道損壞時,還有另一條隧道可用。
如果隧道損壞則無法通行,將需要大量的"Oreon"來修復隧道。
當單個城市被孤立時(其所有互聯隧道都被破壞),則此城市無法製造"Oreon",最終將會導致城牆被破壞。
您作為國土防禦部的負責人,有責任確保所有城市在任何時候,至少通過一條互連的隧道保持通行。
面對防禦部隊中有限的人員,您必須確定使用最少人數的人來保護哪個隧道,並且不會讓任何城市被孤立。

Input

輸入第一行包含一個整數T,代表有幾組測資。
每組測資第一行有一個數字N,N代表圍牆城市數量。
城市編號使用大寫英文字母順序編號。
接下來N行,代表城市隧道安全圖,數字代表需要的安全人員數量。
0代表不需要安全人員,也就表示在兩城市間沒有隧道。
每個數字由逗點和空白做分隔。
(安全圖中,第一行第2個數字代表城市A和城市B之間的隧道需要8位安全人員,以此類推)。

Output

對於每組測資,輸出測資編號
接著輸出需要保護哪條隧道,以及該隧道保護人數。
請按隧道保護人數排列
如果人數相同,請按起始城市排列
如果起始城市相同,請按終點城市排列
(起始城市編號一定小於終點城市編號)
格式請參考範例輸出。

Sample Input #1
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
Sample Output #1
Case 1:
B-D 3
D-F 4
E-F 5
C-E 6
A-F 7
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
30823 kevin010411@ ... (傅詳閎) e586
題目說明
278 2022-06-14 15:17