2011年12月5日 星期一

PKU1258-Agri-Net

題目:http://poj.org/problem?id=1258
給定N(...100)個點之間的連線關係,求最小生成樹權重
另需注意本題有以EOF為準的多筆輸入

程式碼:http://codepad.org/zmF8fNh4
非常適合秒斬的題目(炸)
直接套最最最直白天真的Prim、不必Heap優化,O(V^3)開下去
程式的解釋是這樣的
1.整個cycle作V-1次(i)
2..對於所有在生成樹上的點(j)
......樹上點j連外邊(k)
......試找出最小的一條邊加入生成樹

是適合初學者的裸題

沒有留言:

張貼留言