※ 引述《AcmeChimera (The Agent of God)》之銘言： : ※ 引述《Favonia (00010110110001101010100)》之銘言： : : 超熱血用 latex 排版線代解答以後才發現到 3:00 了!! : : 在我看來好像是 I2A 第二版 p.693 下面問題 26-3 的一般化版本， : : 每個點都連到 s 或 t（看是虧本還是賺錢），然後用 capacity = inf 的 : : 邊來限制 minimum cut 的位置。（同樣的技巧） : : 奇怪了，如果是這個，我記得去年我有講過 :X : 不懂耶 可以請你講清楚一點嗎? 1. 首先給個 s,t 然後所有礦坑是一個點 xi 2. 如果要先挖礦坑 i 才能挖礦坑 j 則 cap(xj->xi)=inf 3. 如果礦坑 i 是賺 a 圓，cap(s->xi)=a 如果礦坑 i 是虧 a 圓，cap(xi->t)=a 4. 其他 cap = 0 ----------------------------------------------------- unformal proof: 考慮 min cut 的位置，以下用 min cut 的左邊稱做有 s 的那一群點， 用右邊稱做有 t 的那一堆點。 我們可以把右邊的點視為 "不挖"，左邊的點視為 "挖"。 因為 min cut 大小有限，不可能有一個 cap=inf 的邊通過這個 cut 所以關係會正確（也就是如果要挖 i 才能挖 j 不可能 xj 在左邊 xi 在右邊） 又，這個 cut 的大小會等於所有： 所有賺錢的不挖的點的總合 + 所有虧錢的挖的點的總合 假設 cut 大小為 C 則利益 = 所有賺錢的挖的點的總合 - 所有虧錢的挖的點的總合 = 所有賺錢的點的總合 - C 前面是個常數，所以 C 的最小值會導致利益的最大值。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.45