※ 引述《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