※ 引述《DJWS (...)》之铭言：
: ※ 引述《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上。
http://perso.ens-lyon.fr/eric.thierry/Graphes2010/amaury-pouly.pdf
我看的是这个, 就是因为如同内文提到, 这提可以用另一种解法, 就想说一起看看证明
是长什么样子, 没想到不只样子有差, 连要怎么转化都有点疑惑.
另一种解法在UVA 的forum还有一个本质相同 但是我想是另一种变形的方式,
另外看不出来cost在每个iteration有变化是因为每个arc的e.cost并没有变化阿?
( http://mycodebattle.com/2014/10/UVa-10806/ )
这边指的cost是指走过arc的cost, 而不是total cost. 这也是理论里面说每个
iteration需要变化的地方 所以我想是哪里理解错误吧?
另外我还会去看一下 最小费用流 跟 最小费用最大流的差别 ORZ
恳请解惑~~
谢谢~