c495: 四、次小生成樹(SBMST)
標籤 :
通過比率 : 100% (8 人 / 8 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2018-01-28 15:05

內容

  給你一張圖,請選出一些邊使得整張圖連通,並輸出最小、次小的兩種權重和。

輸入說明

每筆測試資料的首行會有兩個正整數N,M以空格隔開。

接下來有M行,每會有三個非負整數a,b,w,代表編號a,b的點之間有一條邊,權重是w。

輸出說明

輸出最小生成樹、次小生成樹的權重和,以空格隔開為一行,你可以假設答案必定存在。

範例輸入
//輸入範例1
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

//輸入範例2
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10
範例輸出
//輸出範例1
110 121

//輸出範例2
37 37
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (7%): 1.0s , <10M
不公開 測資點#1 (1%): 1.0s , <10M
不公開 測資點#2 (27%): 1.0s , <1M
不公開 測資點#3 (1%): 1.0s , <1M
不公開 測資點#4 (1%): 1.0s , <1M
不公開 測資點#5 (60%): 1.0s , <50M
不公開 測資點#6 (1%): 1.0s , <50M
不公開 測資點#7 (1%): 1.0s , <10M
不公開 測資點#8 (1%): 1.0s , <10M
提示 :

本題共有三個子題,每一子題可有多筆測試資料:
第一子題的測試資料 N=2,M≤105,全部解出可獲8分;
第二子題的測試資料 N≤103,M≤5×103,全部解出可獲29分;
第三子題的測試資料 N≤105,M≤5×105,全部解出可獲63分。
所有測試資料,1≤a,b≤N,w≤109

標籤:
出處:
板橋高中模擬賽 [編輯:
baluteshih (波路特石)
]


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