※ 引述《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 的问题了。
所以没人想要讨论这种奇怪的东西。