推 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第八页的地方似乎就是这题..只是我看不懂他的解法..