c495.
四、次小生成樹(SBMST)
內容
給你一張圖，請選出一些邊使得整張圖連通，並輸出最小、次小的兩種權重和。
輸入說明
每筆測試資料的首行會有兩個正整數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
不公開 測資點#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
不公開 測資點#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
提示 ：
本題共有三個子題，每一子題可有多筆測試資料：
第一子題的測試資料 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 |
|
c495 | 258 | 2022-10-14 12:51 |