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