Re: [問題] 最大流最小費用問題

[DJWS (...)]

※ 引述《saladim (殺拉頂)》之銘言：
: :            中文 最小費用最大流
: :            英文 minimum cost maximum s-t flow  古代文獻經常省略s-t
: : 我猜你看到的是 中文 最小費用流         的SSPA演算法。那是不一樣的主題。
: :                英文 minimum cost flow
: http://perso.ens-lyon.fr/eric.thierry/Graphes2010/amaury-pouly.pdf
: 我看的是這個, 就是因為如同內文提到, 這提可以用另一種解法, 就想說一起看看證明
: 是長什麼樣子, 沒想到不只樣子有差, 連要怎麼轉化都有點疑惑.

跟我猜的一樣，你看的這篇標題就寫著 minimum cost flow 啊。
不一樣的兩個問題，無論你怎麼轉化都轉不過去。

: 另一種解法在UVA 的forum還有一個本質相同 但是我想是另一種變形的方式,
: 另外看不出來cost在每個iteration有變化是因為每個arc的e.cost並沒有變化阿?
: ( http://mycodebattle.com/2014/10/UVa-10806/ )

int u = ed;
while (u != st)
{
    edges[p[u]].flow += a[ed];
    edges[p[u] ^ 1].flow -= a[ed];
    u = edges[p[u]].from;
}
return true;

剩餘容量變了，圖上多出許多反方向的邊，也就是負的cost的邊。

: 這邊指的cost是指走過arc的cost, 而不是total cost. 這也是理論裡面說每個
: iteration需要變化的地方  所以我想是哪裡理解錯誤吧?

你看的文獻就不對，要怎麼跟你討論？
但是你說的大致上是正確的，
無論是　最小費用流　還是　最小費用最大流　的SSPA都是如此。

: 另外我還會去看一下 最小費用流 跟 最小費用最大流的差別 ORZ

建議你找英文的資料，因為中文網路上幾乎沒有人把這件事搞清楚，尤其是競賽選手。
圖論算法強者tarjan有寫一本網路流的書，
它裡面有稍微提到 minimum cost maximum flow，
可以加減參考看看。

https://books.google.com.tw/books?id=m1rAB3uWwBwC

: 懇請解惑~~
: 謝謝~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.80.89
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1427595099.A.01F.html
→ saladim: 剩餘容量變了 會影響cost嗎? 邊一開始就建好了 後面不會
→ saladim: 增加跟減少了吧?
→ saladim: 我指的是那篇blog的實作方式.....
→ DJWS: 本來沒有反方向的邊，後來有了，也就連帶產生-cost
→ DJWS: 他的實作方式是預先都建好反方向的邊  用xor 1得到反方向的
→ DJWS: 邊  然後一開始就設定好+cost和-cost  所以他其實還是有變
→ DJWS: 只是一開始就把所有變化預先弄好
→ DJWS: 然後每次的最短路徑的cost也都通通不一樣
推 FRAXIS: saladim 你說的 cost 改變 是指改變 reduced cost 還是？
→ saladim: 指的是改變reduced cost...而reduced cost就是會變動到
→ saladim: 毎根edge的cost ==> Cost' = Cost + Pi(v) - Pi(u)
→ saladim: 我上面說的是 minmum cost flow的部分, 問題在於minmum
→ saladim: cost "max flow" 是否同樣適用同樣理論? 如果是的話 為
→ saladim: 何實作裡面edge cost並沒有變化(在residue graph了)
→ saladim: 若是兩個問題不能用同一理論處理 那就要去找到為什麼那
→ saladim: 樣寫可以得到minmum cost max flow....所以問題分成兩部
→ saladim: 份啦~~~~
→ DJWS: Cost' = Cost + Pi(v) - Pi(u) 這個東西就是把權重調成非負
→ DJWS: 方便實施dijkstra最短路徑演算法
→ DJWS: 這個技巧在CLRS的johnson's algorithm也有用過
→ DJWS: 前面提到 會有反向邊與-cost出現  如果不調整成非負
→ DJWS: 那麼只能用floyd-warshall或bellman-ford複雜度較高的方法
→ DJWS: 然後古代的文獻  基本上會把這個叫做potential什麼什麼的
→ DJWS: 而不會介紹他有調成非負權重的功效
→ DJWS: 這個東西是optional的  你有做或沒做  都不會影響正確結果
→ DJWS: 時間複雜度差個O(V^2)而已
推 FRAXIS: 應該沒有差到 V^2 那麼多吧.. 感覺 V^2 好大啊..
→ saladim: 再研究一下...文中貼出的參考資料調成非負跟reduced cost
→ saladim: 是兩件事情...而且發現這兩種問題 其實是有點不一樣 只
→ saladim: 不過是有些引理相同.....有一些本質上差異....
→ saladim: ㄟ 等等 再研究一下好惹 @-@
→ DJWS: 我說錯了  差V才對
→ DJWS: 一開始我不知道你講的 reduced cost 是在講什麼  我用猜的
推 FRAXIS: reduced cost 是 mathematical programming 的概念
→ FRAXIS: 你可以上 wiki 看解釋
→ FRAXIS: 應用到 shortest path 的問題上時 就變成沒負邊的圖
→ DJWS: 因為他一開始都沒有提到 "reduced cost" 這個詞彙
→ saladim: 雖然還沒全懂 似乎是這樣: No negative cycle => Cost'會
→ saladim: >=0 ==> 所以可用Dijk所以reduced cost在此變成非負!!
→ saladim: 又沒有negative cycle跟integer cost就有optimal sol. 故
→ saladim: 得解...雖然就是各位先進所說的 用我的理解走一遍 ORZ
→ saladim: 其他有提到的再繼續看.....@-@||
→ saladim: (min cost flow跟 min cost max flow有什麼關聯還沒懂..)
推 FRAXIS: 其實 min cost flow 有很多變化形.. 所以很難搞清楚..