PKU3662-Telephone Lines

題目：http://poj.org/problem?id=3662
給一張有N(1000)個點編號1...N，P(10000)條邊的帶權無向圖
現在FJ想從中選一些邊來架電話線，好讓點編號1和編號N連通
架電話線的費用算法是所選的所有邊中，最大的那一條權重

並且電話公司提供了FJ一些優惠，其中K條邊是免費的
問FJ最少要花多少錢、架不起來要輸出-1


程式碼：http://codepad.org/8qgRRFhL

假如K=0的話，這就成了一個最小瓶頸生成樹問題
不過現在有一些邊可以無視權重來架設、我們卻不知道該從哪裡開始架設

於是考慮反推：我們試著計算當FJ付出x元的時候，需要的免費邊數f(x)是多少
很顯然地，付越多錢連通性就越高，x越大f(x)就越小、滿足二分搜尋的條件

所以就二分答案，對於每一次測試x，如果邊權重<=x就設長度0、否則設長度1
如此一來求最短路就可以知道付x元要跟電話公司凹多少免費線了