回分類題庫
d162: Minimum Spanning Tree
出處:

Difficulity : 1
Accepted : 2 Times | Submit :77 Times | Clicks : 1633
Accepted : 2 Users | Submit : 11 Users | Accepted rate : 18%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2010-03-23 15:55

Content :

給定一個無向連通圖G = (V, E),以及權重函式w: E → N,我們稱G的一個連通子圖T = (V, E')為Minimum Spanning Tree是指|E'|為|V| - 1,且|E'|權重之和是所有滿足此條件的連通子圖中最小的。請撰程式計算出Minimum Spanning Tree。

Input :

輸入為多筆,每一筆的第一行為圖型的頂點數 n, 0 < n ≤ 1000.
接下來有 n 行,每一行有 n 個整數。第 i 行的第 j 個數字代表邊(i, j)上的權重w(i, j), 0 < w(i, j) ≤ 1024, i ≠ j. 不過w(i, i) = 0,代表圖中沒有self-loop。

Output :

針對每筆測試資料,輸出一行數字,為該圖Minimum Spanning Tree邊上之權重總和。

Sample Input :

5
0 1 9 7 5
1 0 11 19 17
9 11 0 13 23
7 19 13 0 29
5 17 23 29 0

Sample Output :

22

Hint :


  

Author :

(管理員:yuhanlyu)

  Solve it!   Status Forum (1)

C++
C
JAVA
70642. QQQ (278 ms , 8478KB)
18886. yuhanlyu (282 ms , 4150KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡