c495. 四、次小生成樹(SBMST)
Tags :
Accepted rate : 110人/150人 ( 73% ) [非即時]
評分方式:
Strictly

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

Content

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

Input

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

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

Output

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

Sample Input #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
Sample Output #1
//輸出範例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 (59%): 1.0s , <50M
不公開 測資點#6 (1%): 1.0s , <50M
不公開 測資點#7 (1%): 1.0s , <10M
不公開 測資點#8 (1%): 1.0s , <10M
不公開 測資點#9 (1%): 1.0s , <50M
Hint :

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

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

Status Forum 排行

ID User Problem Subject Hit Post Date
32469 lai.abc8660@ ... (alan lai) c495
範測錯誤
444 2022-10-14 12:51