※ 引述《DJWS (...)》之銘言：
: ※ 引述《saladim (殺拉頂)》之銘言：
: : 看了一些人寫的最大流最小費用解法, 常見的實作法如下:
: ^^^^^^^^^^^^^^
: 中文 最小費用最大流
: 英文 minimum cost maximum s-t flow 古代文獻經常省略s-t
: : http://mycodebattle.com/2014/10/UVa-10806/
: 這題大可不必使用最小費用最大流。
: 跑兩次最短路徑就解決了。
: 跑第二次之前，先把第一次的最短路徑，邊權重改負值。第二次是從終點到起點。
: : 但是後來去翻找相近的理論說明, 比較接近的是Successive Shortest Path Algorithm
: 是的，最小費用最大流的常見算法是SSPA。
: : 不過問題來了, SSPA的演算法中, 看起來Cost會隨著每次的iteration變化, 跟開頭
: : 所提的那種實作方式, 似乎有所不同, 常見的做法是不會有變化的
: ^^^^^^^^^^^^^^
: 都是有變化的，包括你給的連結。
: : 而且看SSPA的證明裡面還有什麼pseudo flow啦 , potential function啦
: : imbalance啦 Supply/Demand Vertex啦, 現在小的看不出來怎麼把這個理論
: : 轉化成大家常用的實作方法, 是否哪位先進可以告訴我哪裡理解錯誤呢?
: 請你給個參考資料，寫個註解，不然怎麼討論？大家憑空瞎猜你哪裡理解錯誤嗎？
: 根據你提到的關鍵字
: 我猜你看到的是 中文 最小費用流 的SSPA演算法。那是不一樣的主題。
: 英文 minimum cost flow
: 如果是orlin那一本網路流，它裡面只有介紹最小費用流，沒有介紹最小費用最大流。
: : 就是說常見的實作法是從哪個理論來的, 如果是從SSPA來的, 為什麼又有這麼多地方
: : 轉化不過去, 可否幫忙說明轉化方法呢?
: 我猜你看到的是 最小費用流 而非 最小費用最大流。
: : 謝謝
: : P.S. 沒法把所有SSPA說明打上因為有困難度 抱歉
: 正常人都沒有辦法把那一堆數學式子東西打在BBS上。
http://perso.ens-lyon.fr/eric.thierry/Graphes2010/amaury-pouly.pdf
我看的是這個, 就是因為如同內文提到, 這提可以用另一種解法, 就想說一起看看證明
是長什麼樣子, 沒想到不只樣子有差, 連要怎麼轉化都有點疑惑.
另一種解法在UVA 的forum還有一個本質相同 但是我想是另一種變形的方式,
另外看不出來cost在每個iteration有變化是因為每個arc的e.cost並沒有變化阿?
( http://mycodebattle.com/2014/10/UVa-10806/ )
這邊指的cost是指走過arc的cost, 而不是total cost. 這也是理論裡面說每個
iteration需要變化的地方 所以我想是哪裡理解錯誤吧?
另外我還會去看一下 最小費用流 跟 最小費用最大流的差別 ORZ
懇請解惑~~
謝謝~