PKU1789-Truck History

題目：http://poj.org/problem?id=1789
(這英文題敘真是他媽的難懂…)
簡言之，有N個點(2...2000)的無向帶權圖、由N個字串來代表
不同點之間連線的權重，就是字串間「相應位置字母不同的各數」
好比說aabca和bbbca的距離就是2
試著選N-1條邊讓全點連通，選中的權重和Q、讓1/Q最大


程式碼：http://codepad.org/58DvK6kU
讓1/Q最大，就是讓Q最小、所以就是求最小生成樹…
以N的數據範圍來說，O(V^2)的簡單Prim會是時間和編程複雜度最平衡的作法
(更甚者因為是「完全圖」，任何優化幾乎使不上力、還可能更慢)
定義數組least[n]表示「節點n和目前最小生成樹的最短距離」、如果n是樹上節點則定-1
第一輪任選起點least[0]=0、其餘無限大
如此作V輪(選V個點加入最小生成樹)
每輪都是找出和樹距離最短的點、加入生成樹、由此點更新各點最短距

教育意義不錯的一道題目(惟獨那題敘…)