作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 最大流最小費用問題
時間Sun Mar 29 10:11:35 2015
※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1427595099.A.01F.html
1F：→ saladim: 剩餘容量變了 會影響cost嗎? 邊一開始就建好了 後面不會 03/29 21:25
2F：→ saladim: 增加跟減少了吧? 03/29 21:25
3F：→ saladim: 我指的是那篇blog的實作方式..... 03/29 21:27
4F：→ DJWS: 本來沒有反方向的邊，後來有了，也就連帶產生-cost 03/29 23:16
5F：→ DJWS: 他的實作方式是預先都建好反方向的邊 用xor 1得到反方向的 03/29 23:17
6F：→ DJWS: 邊 然後一開始就設定好+cost和-cost 所以他其實還是有變 03/29 23:18
7F：→ DJWS: 只是一開始就把所有變化預先弄好 03/29 23:18
8F：→ DJWS: 然後每次的最短路徑的cost也都通通不一樣 03/29 23:19
9F：推 FRAXIS: saladim 你說的 cost 改變 是指改變 reduced cost 還是？ 03/30 06:24
10F：→ saladim: 指的是改變reduced cost...而reduced cost就是會變動到 03/30 09:12
11F：→ saladim: 毎根edge的cost ==> Cost' = Cost + Pi(v) - Pi(u) 03/30 09:13
12F：→ saladim: 我上面說的是 minmum cost flow的部分, 問題在於minmum 03/30 09:14
13F：→ saladim: cost "max flow" 是否同樣適用同樣理論? 如果是的話 為 03/30 09:15
14F：→ saladim: 何實作裡面edge cost並沒有變化(在residue graph了) 03/30 09:16
15F：→ saladim: 若是兩個問題不能用同一理論處理 那就要去找到為什麼那 03/30 09:17
16F：→ saladim: 樣寫可以得到minmum cost max flow....所以問題分成兩部 03/30 09:18
17F：→ saladim: 份啦~~~~ 03/30 09:18
18F：→ DJWS: Cost' = Cost + Pi(v) - Pi(u) 這個東西就是把權重調成非負 03/30 09:22
19F：→ DJWS: 方便實施dijkstra最短路徑演算法 03/30 09:22
20F：→ DJWS: 這個技巧在CLRS的johnson's algorithm也有用過 03/30 09:22
21F：→ DJWS: 前面提到 會有反向邊與-cost出現 如果不調整成非負 03/30 09:23
22F：→ DJWS: 那麼只能用floyd-warshall或bellman-ford複雜度較高的方法 03/30 09:24
23F：→ DJWS: 然後古代的文獻 基本上會把這個叫做potential什麼什麼的 03/30 09:25
24F：→ DJWS: 而不會介紹他有調成非負權重的功效 03/30 09:25
25F：→ DJWS: 這個東西是optional的 你有做或沒做 都不會影響正確結果 03/30 09:28
26F：→ DJWS: 時間複雜度差個O(V^2)而已 03/30 09:29
27F：推 FRAXIS: 應該沒有差到 V^2 那麼多吧.. 感覺 V^2 好大啊.. 03/30 21:45
28F：→ saladim: 再研究一下...文中貼出的參考資料調成非負跟reduced cost 03/31 00:02
29F：→ saladim: 是兩件事情...而且發現這兩種問題 其實是有點不一樣 只 03/31 00:03
30F：→ saladim: 不過是有些引理相同.....有一些本質上差異.... 03/31 00:03
31F：→ saladim: ㄟ 等等 再研究一下好惹 @-@ 03/31 00:05
32F：→ DJWS: 我說錯了 差V才對 03/31 08:52
33F：→ DJWS: 一開始我不知道你講的 reduced cost 是在講什麼 我用猜的 03/31 08:54
34F：推 FRAXIS: reduced cost 是 mathematical programming 的概念 03/31 20:08
35F：→ FRAXIS: 你可以上 wiki 看解釋 03/31 20:08
36F：→ FRAXIS: 應用到 shortest path 的問題上時 就變成沒負邊的圖 03/31 20:09
37F：→ DJWS: 因為他一開始都沒有提到 "reduced cost" 這個詞彙 04/01 09:02
38F：→ saladim: 雖然還沒全懂 似乎是這樣: No negative cycle => Cost'會 04/02 15:25
39F：→ saladim: >=0 ==> 所以可用Dijk所以reduced cost在此變成非負!! 04/02 15:26
40F：→ saladim: 又沒有negative cycle跟integer cost就有optimal sol. 故 04/02 15:27
41F：→ saladim: 得解...雖然就是各位先進所說的 用我的理解走一遍 ORZ 04/02 15:28
42F：→ saladim: 其他有提到的再繼續看.....@-@|| 04/02 15:28
43F：→ saladim: (min cost flow跟 min cost max flow有什麼關聯還沒懂..) 04/02 15:30
44F：推 FRAXIS: 其實 min cost flow 有很多變化形.. 所以很難搞清楚.. 04/02 22:38