PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間9年前 (2015/03/28 12:28)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/5 (看更多)

※ 引述《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