樹上有N(10000)個節點，其中有T個點是重要的
每條邊上有權重代表拔走這條邊的花費，現在想拔走恰好K條邊
使得拔完以後每個連通塊都保有至少一個重要節點
問最小花費
(題設保證拔法一定存在)
程式碼：http://codepad.org/RGa033gv
它一臉長得貪心貪心的
所以天真的想，每次都試看看一條最小的邊能不能拔、直接模擬檢察
這樣O(n^2)直接T
於是想觀察什麼樣的邊會不能拔，假設重要點是黑點、其他是白點
試著朝樹形DP想的時候，想起這類DP葉子的狀態都會很單純、像遞回的終點一般
於是發現了這個性質：
「白色的葉子所屬的邊，拔了一定會葛屁」 (連證明都不必了對吧)
因此先把白色葉子砍光(縮葉縮鏈，讓它直接依賴上一個點)
遞回檢查有沒有造成新的白葉<delete_white函式>
然後得到一個漂亮的黑葉樹，發現它又有另一個不得了的性質：
「黑葉樹上隨便一條邊拔完以後，兩邊都至少有一個黑點」
說明：
1.黑葉樹上至少有兩個黑點 (如果是一個黑點的樹就沒得拔了…)
2.拔走任一條邊以後，兩側都至少仍保有一片黑葉
因為拔邊這個動作只會讓葉子變多、不會變少
最後得到算法如下：
1.對所有的點縮白葉 (delete_white : 白色且分支度1的點縮掉、遞回檢查)
2.把所有邊由小到大排序，對於沒被縮掉的邊就貪心地拔掉它
拔走以後可能會產生新的白葉，再度對兩點執行delete_white
排序部分O(nlgn)
delete_white是不可逆的過程、至多只能縮N-T次，平攤完每次縮都是O(1)、整體O(n)
得總複雜度O(nlgn)
沒有留言:
張貼留言