Codeforces #73 D FreeDiv

題意﹕給了 $N$ 個點，現在接了 $M$ 條藍色邊，一個由藍色邊接成的連通塊稱作藍色領域。現在你可以添加紅色邊使得所有藍色領域都連通起來，但是有限制﹕(1)每點只能接上最多一條紅色邊。(2)每個藍色領域不能接上超過 $k$ 條紅色邊。
根據這個限制，有可能沒法添加紅色邊使得所有藍色領域都連通起來。現問至少需添加多少條藍色邊使得能達成要求？

首先，我們若把所有藍色領域縮成一點，每點標號為 $\min(k, b_i)$ ，當中 $b_i$ 為第 $i$ 個藍色領域的點數。那麼其標號即為限制讓人藍色領域最多可外接多少條紅色邊。現在問題可看成兩種操作﹕
(1) 添加藍邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域，標號為 $\min(b_u+b_v, k)$ 。
(2) 添加紅邊連接領域 $u$ 和 $v$ 。那麼新的點 $w$ 即可看作新的藍色領域，標號為 $(b_u+b_v - 2)$ 。

假定不允許操作(1)(即添加藍色邊)，甚麼時候會不能滿足問題條件？明顯是存在兩個點 $u, v$ 使得 $b_u=b_v=1$ 並只能為這兩點進行操作(2)。甚麼時候可以盡量防止這情況發生？留意當 $b_u, b_v \ge 2$ 操作(2)只會製造一個新點 $w$ 使得 $b_w \ge \max(b_u, b_v)$ ，故不會導致失敗。那麼可以先為標號從大到小排序，順著標號進行操作(2)即可，只要當中有標號少於零的即當作失敗。

如果允許操作(1)，怎樣可以把操作(1)的數量最少又使得條件滿足？可用二分搜索答案。假設你只允許進行操作(1) $p$ 次，你會怎樣進行操作(1)使得用上段的方法添加紅邊後條件滿足？不難留意上段說明失敗的情況只有標號為1的點太多的時候才會發生。要避免這個情況，可以考慮每次把兩個標號為1的點用操作(1)連起來，成為一個標號為 $2$ 的點。再由上段可知，它和標號大於2的點添加紅邊，不會出現失敗情況；它杏標號為1的點添加紅邊，會變成只有一個標號為1的點。故把兩兩標號為1的點用藍邊連接最能防止失敗的情況。

我寫的時候用了STL的priority_queue，結果超時(5秒都超…)。改用STL的make_heap之後剛好4.5秒通過了…另，我認為可以不用二分，直接可以算出應最少用多少次操作(1)。