※ 引述《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上。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.80.104
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1427516911.A.DF7.html