※ 引述《saladim (杀拉顶)》之铭言： : 看了一些人写的最大流最小费用解法, 常见的实作法如下: ^^^^^^^^^^^^^^ 中文 最小费用最大流 英文 minimum cost maximum s-t flow 古代文献经常省略s-t : http://mycodebattle.com/2014/10/UVa-10806/ 这题大可不必使用最小费用最大流。 跑两次最短路径就解决了。 跑第二次之前，先把第一次的最短路径，边权重改负值。第二次是从终点到起点。 : 但是後来去翻找相近的理论说明, 比较接近的是Successive Shortest Path Algorithm 是的，最小费用最大流的常见算法是SSPA。 : 不过问题来了, SSPA的演算法中, 看起来Cost会随着每次的iteration变化, 跟开头 : 所提的那种实作方式, 似乎有所不同, 常见的做法是不会有变化的 ^^^^^^^^^^^^^^ 都是有变化的，包括你给的连结。 : 而且看SSPA的证明里面还有什麽pseudo flow啦 , potential function啦 : imbalance啦 Supply/Demand Vertex啦, 现在小的看不出来怎麽把这个理论 : 转化成大家常用的实作方法, 是否哪位先进可以告诉我哪里理解错误呢? 请你给个参考资料，写个注解，不然怎麽讨论？大家凭空瞎猜你哪里理解错误吗？ 根据你提到的关键字 我猜你看到的是 中文 最小费用流 的SSPA演算法。那是不一样的主题。 英文 minimum cost flow 如果是orlin那一本网路流，它里面只有介绍最小费用流，没有介绍最小费用最大流。 : 就是说常见的实作法是从哪个理论来的, 如果是从SSPA来的, 为什麽又有这麽多地方 : 转化不过去, 可否帮忙说明转化方法呢? 我猜你看到的是　最小费用流　而非　最小费用最大流。 : 谢谢 : P.S. 没法把所有SSPA说明打上因为有困难度 抱歉 正常人都没有办法把那一堆数学式子东西打在BBS上。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.80.104 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1427516911.A.DF7.html