題目連結: http://uva.onlinejudge.org/external/120/12035.html
此題出自 Bangladeshi national Contest, kn看到後覺得有趣又不太懂做便叫我去做這題
題目雖然不是很難, 但做出來還是很有成功感, 所以很興奮的把這題寫下來
題意很簡單, 就是問從vertex特定的degree sequence可否形成一個bipartite graph
一開始會發現N<=20, 就會從枚舉每點屬於bipartite graph的可能性再試可否形成一個bipartite graph
測試可否形成bipartite graph的一部分不難想到可以用maximum flow去解決
這樣的速度大概是 O(2^n * n^3), 而測試數據有500個, 明顯會超時
繼續向這個方向想, 發現該二分圖的左邊和右邊的degree sum必定相等, 否則肯定不能組成一個合理的graph
加了這個checking後應該可以排除很多case, 做少很多次maximum flow
交這個上去也是得到TLE, 而且經過測試後發現計算所有subset of vertex的degree sum已經用了大部份的時間
這題time limit只有一秒, 時限算是非常緊
這是開始去試一些大的test case, 就像20個點每點的degree都是19, 很明顯不能組成bipartite graph
如果暴力試所有點的subset的話, 就會有很多相同的degree sequence要試 (左邊10個19, 右邊10個19)
但事實上應該可以知道該sequence是一樣而不用再試
因此我們可以把相同的degree group在一起, 在暴力分左右時把該degree某個數量的vertex分到左邊
這樣就可以避免重覆地試相同的degree sequence
以這個方法用recursion有技巧地試就以0.857s Accepted了
再想發現我的program很多時候會試多了一倍的可能性, 因為相同的subset會被放到左邊或右邊各一次
因次再加上假如是在試第一個vertex時, 最多只有一半的vertex被分到左邊, 就可以減少試一半的case
加了這個optimization之後以0.476s Accepted
不知道還有沒有更好的方法解決這條問題呢?
Hello!
回覆刪除I am trying very hard this problem with little success. Just keep getting TLE.
I'm not sure what to do anymore...the only resource I found is your blog, but I can't understand chinese and the translation (from gtranslate) is not very clear. Could you give me some ideas, please? :)
I am currently using a meet in the middle approach, so I can find the bitmasks with same degree sum fasterm then run maxflow (i am not sure if the flow is really needed). But only that apparently leads to TLE. ):