※ 引述《FRAXIS (喔喔)》之銘言： : ※ 引述《DJWS (...)》之銘言： : : 然後min cost flow有一些莫名其妙的特例， : 這邊就是我很難搞懂的地方 : : 例如circulation problem/transportation problem之類的。 : : 這些都不是重點，這些只是流量下限為0、supply/demand為0之類的， : : 圖論方式的演算法還是一樣沒變。 : : 線性規劃的演算法可能有差一點點，我沒有仔細去研究。 : 書上大部分都是介紹 min cost circulation problem，因為這可以解其他所有問題。 : 像是 min-cost max flow 、 min-cost flow 、 transshipment 、 transportation : 和 assignment 。 : 理論上是只要解 transshipment 就可以了，因為他跟 circulation problem 是等價 : （線性時間轉換），只是實際上應用有點麻煩。 : 每類問題自己又有分 有向/無向 、 上下限（正負） 、 cost正負 、 : supply/demand 等等變化。 : 雖然有技巧可以把這些都正規化成有向無上下限且cost皆為正， : 但是要記起來挺麻煩的。 : 而且 把 cost 從負變正 和 無向轉有向 還會互相衝突？？ 你寫的那些問題，就是我所謂的莫名其妙的特例。 我覺得這些問題是冷知識，沒有必要鑽研。 事情其實可以很簡單， 考慮 是st還是循環 、 supply/demand 、 上下限 這三件事情就夠了。 最後總是可以用 min cost max st flow 的演算法解決。 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 正規化的方式也很簡單，orlin那本書有介紹。 　1. 下限變不見 　　 　（事先流一些，a supply -k , b supply +k） 　2. -cost變成+cost 　 　 （事先流到滿，residual network完全變反向， 　　　　　　　　　　 　　（cost就完全變號了。SSPA就有這種情況。） 　3. feasible flow變成max st flow （新增st，s連到supply，demand連到t，很直覺。) 只有這三步。很直覺，應該不會太難記。 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 至於無向邊，幾乎沒人討論。 因為無向邊必須規定如何流動，這很難搞。 例如可以同時雙向對流，又例如只能選擇一個方向流。 前者就很智障，不就是來回不斷流來流去，單純衝流量嗎？沒有討論意義。 後者的重點，已經不是流的問題了，而是 graph orientation 的問題了。 所以沒人想要討論這種奇怪的東西。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.70.154 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1428076497.A.828.html ※ 編輯: DJWS (111.250.68.114), 04/05/2015 07:14:09