※ 引述《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/cn.aspx?n=bbs/Prob_Solve/M.1428076497.A.828.html ※ 编辑: DJWS (111.250.68.114), 04/05/2015 07:14:09