推 FRAXIS: http://www.slideserve.com/xaviera-bowers/6486226 01/13 01:55
→ FRAXIS: 第八頁的地方似乎就是這題..只是我看不懂他的解法.. 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...

http://www.slideserve.com/xaviera-bowers/6486226第八頁的地方似乎就是這題..只是我看不懂他的解法..