※ 引述《DJWS (...)》之铭言： : 推 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... 我好像大概了解了，不知道有没有错.. 输入为A，然後前处理计算P[i] = A[i] - A[i+1]，我们要求解B[]。 令 X[i] 为变数表示 A[i] 的增加量。 Y[i] 为变数表示 A[i] 的减少量。 所以 B[i] = A[i] + X[i] - Y[i]，目标是要极小化X[i] + Y[i]的总和。 我们希望-D <= B[i] - B[i+1] <= D 也就是 -D <= A[i] + X[i] - Y[i] - A[i+1] - X[i+1] + Y[i+1] <= D 也就是 -D - P[i] <= X[i] - Y[i] - X[i+1] + Y[i+1] <= D - P[i] 拆成两个限制式，然後转成标准式 X[i] - Y[i] - X[i+1] + Y[i+1] + S[i] = D - P[i] (1) X[i] - Y[i] - X[i+1] + Y[i+1] - T[i] = -D - P[i] (2) 从(1)和(2)可知S[i] + T[i] = 2D，所以其实只要 保留其中一个限制式，然後设定S或是T的上限为2D即可。 最後把这n-1个等式加总，然後两边都乘以负一，得到一个新的多余的限制式。 但是结果会是一个min-cost flow的形式，就可以用min-cost flow解了。 在(1)和(2)，我们可以多作一些处理。 当D < P[i]时，(1)的右边 < 0，所以可以设定S[i]的下界为P[i] - D。 当-D > P[i]时，(2)的右边 > 0，所以可以设定T[i]的下界为-P[i] - D。 在这两种case，右手边都可以化简为0。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.149 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1421169993.A.910.html ※ 编辑: FRAXIS (129.170.194.148), 01/14/2015 23:59:13