※ 引述《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 的問題了。
所以沒人想要討論這種奇怪的東西。