Re: [問題] Reduce LP成Min-cost flow
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間10年前 (2015/01/13 23:21)推噓0(0推 0噓 0→)留言0則, 0人參與討論串4/5 (看更多)
推
01/13 01:55,
01/13 01:55
→
01/13 01:55,
01/13 01:55
我也看不太懂，我猜是這樣：
令a[i]=h[i]-h[i+1]
h[i]加1 <=> a[i-1]減1 且 a[i]加1。
h[i]減1 <=> a[i-1]加1 且 a[i]減1。
h[i]加1，可以視作「一單位的水從a[i-1]流到a[i]」。
h[i]減1，可以視作「一單位的水從a[i]流到a[i-1]」。
因此設定a[i-1]到a[i]是無向邊（只能選其中一個方向流動）。
h[i]加1或者減1，minimize的對象就加1。
因此該無向邊費用設定成1。
當無向邊的流量越少，則minimize的對象就越小。
因此設定為最小費用流。
若a[i]<-d，则至少要从别的地方拿个1，且不能多于|a[i]|-d个1；
因此从点i向t连边，容量下界|a[i]|-d，上界|a[i]|+d，费用0。
題目規定相鄰兩數差a[i]的範圍是 -d ~ +d （d是正數）
a[i]<-d 就必須把a[i]補到變成-d，至少需要補-d - a[i] = |a[i]| - d。
把邊拉往target，是為了強迫source一定要補東西進來，
要從哪個入口補入都可以（每一個h[i]都可以調整）
設定出口的容量上下限，就能控制入口補多少東西進來。
大概就是這種感覺
然後我覺得他的source和target顛倒過來應該也OK...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.91.104
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1421162477.A.7A0.html
※ 編輯: DJWS (111.250.91.104), 01/13/2015 23:30:29
※ 編輯: DJWS (111.250.91.104), 01/13/2015 23:40:03
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30