※ 引述《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 从负变正 和 无向转有向 还会互相冲突？？ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.167 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1428066102.A.7FA.html ※ 编辑: FRAXIS (129.170.195.167), 04/03/2015 21:03:19