給你一張圖,請選出一些邊使得整張圖連通,並輸出最小、次小的兩種權重和。
每筆測試資料的首行會有兩個正整數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
本題共有三個子題,每一子題可有多筆測試資料:
第一子題的測試資料 N=2,M≤105,全部解出可獲8分;
第二子題的測試資料 N≤103,M≤5×103,全部解出可獲29分;
第三子題的測試資料 N≤105,M≤5×105,全部解出可獲63分。
所有測試資料,1≤a,b≤N,w≤109。
ID | User | Problem | Subject | Hit | Post Date |
32469 | lai.abc8660@ ... (alan lai) | c495 | 444 | 2022-10-14 12:51 |