題目：http://poj.org/problem?id=2485
給出帶權無向圖N(3...500)個點間的連線距離
想要選一些連線建造高速公路
所有點之間都有路可通的前提下，最長的那條邊要盡量小
問那條邊的權重是多少？
程式碼：http://codepad.org/5g3QzDUL
最小生成樹是出了名的貪心
如果深刻理解Kruskal法的話
就不難猜到「邊權總和最小」和「最長邊盡量小」這兩個要求
其實是同時成立、並行不悖
因此隨意選一種最小生成樹算法、更新最長的邊、收工
可以參考算法導論：最小生成樹章末思考題：最小瓶頸生成樹
所謂"瓶頸邊"就是生成樹上的最長邊，
瓶頸這個生動的形容詞也是富暗示性啟發性的
沒有留言:
張貼留言