時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
若干城牆城市以雙向隧道相連。保護每條隧道需要指定人數。請選擇需要保護的隧道，使所有城市仍可透過受保護的隧道互相到達，且所需的總人數最少。 城市依序以英文字母 A、B、C、… 標示。輸入矩陣給出各對城市間隧道所需的人數，0 表示兩城市間沒有隧道。
輸入格式
第一行為測試資料數 T。每筆先給城市數 n，再接著 n 行，每行 n 個以逗號分隔的整數，表示隧道矩陣。逗號旁可能有空白。
輸出格式
每筆先輸出 Case k:，k 從 1 起算。接著列出所選隧道，每行格式為 A-B w，表示保護 A 與 B 之間的隧道需要 w 人；兩個城市字母由小到大排列。依範例，隧道依所需人數由少到多列出。
本題庫測資範圍
本題庫目前測資中的非零邊權重互異，因此最小生成樹唯一；原題未規定等權重時的取捨。
題目來源：UVa 1208 — Oreon。 原題：https://onlinejudge.org/external/12/1208.pdf
範例測資
範例輸入 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
範例輸出 1
Case 1: B-D 3 D-F 4 E-F 5 C-E 6 A-F 7
請先登入後再提交程式碼
討論與題解
載入討論區…