PKU2377-Bad Cowtractors

題目：http://poj.org/problem?id=2377
給N個點M條邊(最多1000,20000)，求最大生成樹權重
求不出來必須輸出-1

(最近喜歡秒斬算法裸題…)


程式碼：http://codepad.org/XVxRFof8
經典問題，套個Kruskal就出來
其實這題本來要考的是：最大生成樹和最小生成樹是同一個問題嗎？
那麼只要精通「最小生成樹有貪心選擇性質」證明的朋友
(或者不那麼精通的朋友…：
http://zh.wikipedia.org/wiki/Kruskal%E6%BC%94%E7%AE%97%E6%B3%95)
透過「選擇的邊數固定」，很容易推出/猜對：
優先選最小邊是最小生成樹、反之亦然

在Kruskal來說，本來由小到大排序、改成由大到小，就完工