2016年2月26日 星期五

[HOJ 136][IOI 2007]Training

HOJ生病惹QQ,因此我在這裡做了題目備份,請參考~

換句話說,題目希望不產生偶環的前提下,總權重最大化
感覺會超多奇環相互交錯再一起耶......好複雜QQ

我們先來討論兩個奇環的情況
1. 不相交:合法情況,之後再深入討論
2. 相交於一點:合法情況,之後再深入討論
3. 重合於任何邊:形成偶環了,不合法!
(原來奇環也只有這樣嘛www)

那些會在樹上形成偶環的非樹邊可以直接刪除了

我們來嘗試構造一個樹形$DP$
首先,我們必須避免同一條邊被多個環同時使用
因此,狀態中必須包含哪些邊被用過了
由於每個點的度數不超過$10$
因此我們可以利用位元壓縮的技巧,用$DP[u][s]$代表以$u$為節點的子樹中,連到$u$的邊 (包含樹邊和非樹邊) 的子集合$s$ (用$bit\ mask$表示) 被用過了,總權重最多多少

於是,我們可以枚舉所有「樹上路徑」會通過$u$的邊$e$,然後用以下方式直接算出每個$DP[u][s]$:
圖片來源:http://www.ioinformatics.org/locations/ioi07/contest/solutions.pdf
其中除了以下這個 (稱作$subtree$) 需要遞迴計算之外,其他的都已經在先前遞迴到子樹時計算好了
可是這樣要計算$subtree$的時候還要想辦法把兩端都在$subtree$內的非樹邊分離出來
想一想複雜度好像很容易又爛掉了QQ

沒關係,不用遞迴了,我們先算好只加一個環的部分

然後依照$bit\ mask$中$1$的數量由小到大更新$DP[u]$ (這時候如果用到的邊沒有重複就可以直接相加來更新更大的$DP[u]$了)
為了節省時間,只更新「加一個環」(用掉兩條邊) 和「加一棵子樹」(用掉一條邊) 的情況,然後順著$DP[u]$的更新順序就可以把所有情況都考慮進去了

小提醒:請記得答案是所有邊的權重總和減掉算出來的$DP$

時間複雜度:$O(N^{2}+NM+2^{10}M)$ (預處理從$u$走到$v$要先走連到$u$的第幾條邊、預處理一條邊是$u$的第幾條邊、更新$DP$)

code:

請參考這裡

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原