c496: 一、第k小瓶頸樹(Kth-bottleneck)
標籤 :
通過比率 : 67% (4 人 / 6 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2018-11-12 23:49

內容

  一張圖、一棵樹、一條路徑上權重最大的邊,被稱為「瓶頸」。

  現在給你一張圖,問你嚴格第K小瓶頸生成樹的瓶頸權重是多少?

輸入說明

每筆測試資料的首行會有三個正整數N,M,K以空格隔開,代表給予的圖有N個點M條邊。

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

輸出說明

輸出嚴格第K小瓶頸樹的瓶頸權重,如果不存在請輸出-1。

範例輸入
//輸入範例1
5 6 2
3 5 8
1 3 6
2 5 7
1 4 9
2 4 4
1 2 2

//輸入範例2
5 6 4
3 5 8
1 3 6
2 5 7
1 4 9
2 4 4
1 2 2
範例輸出
//輸出範例1
8

//輸出範例2
-1
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (6%): 1.0s , <10M
不公開 測資點#1 (1%): 1.0s , <10M
不公開 測資點#2 (1%): 1.0s , <10M
不公開 測資點#3 (18%): 1.0s , <50M
不公開 測資點#4 (1%): 1.0s , <10M
不公開 測資點#5 (1%): 1.0s , <50M
不公開 測資點#6 (20%): 1.0s , <50M
不公開 測資點#7 (1%): 1.0s , <50M
不公開 測資點#8 (1%): 1.0s , <10M
不公開 測資點#9 (48%): 1.0s , <50M
不公開 測資點#10 (1%): 1.0s , <50M
不公開 測資點#11 (1%): 1.0s , <50M
提示 :

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

 

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


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」