※ 引述《bleed1979 (口德是一种美德)》之铭言：
: 标题: Re: [问题] Reduce LP成Min-cost flow
: 时间: Tue Jan 13 00:39:39 2015
: ※ 引述《FRAXIS (喔喔)》之铭言：
: : 在网络上看到一个问题：
: : 给定一个整数阵列 A ，一个正整数D，要求设计一个算法把
: : A 修改成 B （长度不变），使得 B 中相邻的元素的差值都小于D，
: : 且最小化 |A[i] - B[i]| 的总和。
: : http://www.careercup.com/question?id=5207197178920960
: : 我自己想的解法是使用Linear programming，但是我又感觉这
: : 问题似乎是可以用Min-cost flow来解的，只是我找不出来怎么作。
: : 不知道有没有人有其他解法？
: : 考虑一般性的情况，给定一个LP的 formulation ，有没有什么
: : 技巧，在某些条件满足的状况下，可以把LP转成Min-cost flow？
: : 因为我觉得设计LP比想出network flow的模型容易许多。
:
: 推 dreamoon: 真是巧妙的题目... 01/13 13:43
: → dreamoon: 有上下界的最小花费网络流 01/13 13:44
: 推 dreamoon: 是说我可不觉得任何LP都可以换成min-cost flow @@ 01/13 13:47
我知道LP不可能都可以换成min-cost flow，因为min-cost flow是LP的特例。
但是在某些情况下，先设计好LP，然后就可以系统化的转换成min-cost，
这会比直接设计min-cost来的容易一些。
比如说这一题：
https://www.byvoid.com/blog/noi-2008-employee
实际上的想法是这样，先设计一个LP，其限制式为
Ax = b (1)
而一个min-cost flow的限制式必须满足
Yx = b, Y的值为-1, 0, 1，每一列必须有刚好一个1和-1，b为整数且总和为0。
只要Y满足这条件，就可以使用min-cost flow算法。
（x的限制式必须是非负，或是在一个正整数区间）
所以要解(1)，就对A矩阵作列运算，想办法转成满足min-cost flow条件的Y矩阵即可。
（也可以对行作scaling，只是这题用不到）
然后回到我原本问的题目，我可以设计LP如下：
B[i]是变量，代表修改后的值，Y[i]代表修改A[i]的cost，我们可得到下列关系
B[i] - B[i+1] <= D
B[i+1] - B[i] <= D
B[i] - A[i] <= Y[i]
A[i] - B[i] <= Y[i]
最后两个不等式是来描述Y[i] = |A[i] - B[i]|。
因为是对Y[i]的总和作极小化，所以在最佳解时Y[i] = |A[i] - B[i]|
但是我怎么想也没办法把这LP跟我google到的min-cost flow解答作连结。
而且我也不太知道那个min-cost flow的解答到底是不是正确的，所以
才上来发问。