c495. 四、次小生成樹(SBMST)
標籤 :
通過比率 : 110人/150人 ( 73% ) [非即時]
評分方式:
Strictly

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

內容

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

輸入說明

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

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

輸出說明

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

範例輸入 #1
//輸入範例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
//輸出範例1
110 121

//輸出範例2
37 37
測資資訊:
記憶體限制: 512 MB
提示 :

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
32469 lai.abc8660@ ... (alan lai) c495
範測錯誤
457 2022-10-14 12:51