我也看不太懂，我猜是这样： 令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://webptt.com/cn.aspx?n=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