題目 2461:
信息學(xué)奧賽一本通T1555-次小生成樹
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 8 解決: 3
題目描述
原題來自：BeiJing 2010 組隊(duì)賽
給定一張 N 個(gè)點(diǎn) M 條邊的無向圖，求無向圖的嚴(yán)格次小生成樹。
設(shè)最小生成樹的邊權(quán)之和為 sum，嚴(yán)格次小生成樹就是指邊權(quán)之和大于 sum 的生成樹中最小的一個(gè)。
輸入格式
第一行包含兩個(gè)整數(shù) N 和 M，表示無向圖的點(diǎn)數(shù)與邊數(shù)；
接下來 MM 行，每行三個(gè)數(shù) x,y,z，表示點(diǎn) x 和點(diǎn) y 之間有一條邊，邊的權(quán)值為 z。
輸出格式
包含一行，僅一個(gè)數(shù)，表示嚴(yán)格次小生成樹的邊權(quán)和。
數(shù)據(jù)保證必定存在嚴(yán)格次小生成樹。
樣例輸入
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
提示
數(shù)據(jù)范圍與提示：
對(duì)于全部數(shù)據(jù)，1≤N≤105,1≤M≤3×105 ，數(shù)據(jù)中無向圖無自環(huán)，邊權(quán)值非負(fù)且不超過 109 。
標(biāo)簽