題目可轉化為一堆 bonus[ai] + bonus[bi] ≥ k 的不等式
By 直覺, 一定存在一 optimal solution 其中 bonus[i] 為 k/2 的倍數 (0, k/2, k)
(其實好像可以 prove, 不過我不懂)
先假設上面的前題正確, 但是三種可能性很難處理, 所以先統一所有 bonus 都是 k/2, 那樣就只剩下兩種可能性
再轉化為 (其實這 step 不是這樣想出來的, 而是由 solution 推導出來):
bonus1[ai] + bonus2[bi] ≥ k/2
bonus1[bi] + bonus2[ai] ≥ k/2
其中 bonus1[i] 和 bonus2[i] 都是 0 或 k/2
把 (bonus1[ai], bonus2[bi]) 視為一條 edge, 會得到一 bipartite graph, 而且要做的其實就是 minimum vertex cover!
由 König's theorem 可知, 對於 bipartite graph, minimum vertex cover = maximum matching
所以之後只要做 matching 再找出 cut 便大功告成
機已屈, 我地隊都唔識做, 邊度搵到solution?
ReplyDelete>>一定存在一 optimal solution 其中 bonus[i] 為 k/2 的倍數 (0, k/2, k)
我個人的想法: 如果將這個問題當作linear programming來看, 可以知道所有extreme point都是兩條線的交點, 從那些constraint的特性來看可以發現intersection都是會在{0, k/2, k}
無搵 solution, 個 solution 係我「估」的
ReplyDelete我一開始估可以用 matching 做, 過左再諗下點解 work