b181: 2. 網路設計
標籤 :
通過比率 : 83% (95 人 / 115 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2008-11-10 11:12

內容

某一城市欲建立都會網路,以使每一區公所均可連線到其他各區公所(可能直接連線或透過其他的區公所間接連線)。假設任兩個區公所之間的佈線成本為已知;每一條網路線均為雙向傳送。請寫一程式,印出哪些區公所之間需要施工佈線,以找出此城市使用最低成本完成此都會網路之佈線架構。

輸入說明

第一列有兩個正整數nm,其中n代表區公所個數(n<=10),區公所代碼為W1W2W3…Wnm代表有m個可能的佈線連結兩區公所。其後有m列,每一列之資料依序為兩區公所代碼,及連接此兩區公所之佈線成本。各項資料之間以一個空白分隔;佈線成本為一正整數。

輸出說明

印出二列。第一列為佈線架構,印出數組資料,每一組資料為兩個區公所代碼,代表此兩個區公所需要施工佈線,每一組資料包含在一對括號之中。第二列為佈線總成本。各項資料之間以一個空白分隔。

範例輸入
7  11
W1 W2 1
W1 W4 4
W2 W3 2
W2 W4 6
W2 W5 4
W3 W5 5
W3 W6 6
W4 W5 3
W4 W7 4
W5 W6 8
W6 W7 3
範例輸出
(W1 W2) (W1 W4) (W2 W3) (W4 W5) (W4 W7) (W6 W7)
17
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
提示 :
標籤:
出處:
97學年度高雄市資訊學科能力競賽 [編輯:
khps9703 (khps)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」