※ 引述《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的解答到底是不是正確的，所以
才上來發問。