※ 引述《saladim (杀拉顶)》之铭言：
: : 中文 最小费用最大流
: : 英文 minimum cost maximum s-t flow 古代文献经常省略s-t
: : 我猜你看到的是 中文 最小费用流 的SSPA算法。那是不一样的主题。
: : 英文 minimum cost flow
: http://perso.ens-lyon.fr/eric.thierry/Graphes2010/amaury-pouly.pdf
: 我看的是这个, 就是因为如同内文提到, 这提可以用另一种解法, 就想说一起看看证明
: 是长什么样子, 没想到不只样子有差, 连要怎么转化都有点疑惑.
跟我猜的一样，你看的这篇标题就写着 minimum cost flow 啊。
不一样的两个问题，无论你怎么转化都转不过去。
: 另一种解法在UVA 的forum还有一个本质相同 但是我想是另一种变形的方式,
: 另外看不出来cost在每个iteration有变化是因为每个arc的e.cost并没有变化阿?
: ( http://mycodebattle.com/2014/10/UVa-10806/ )
int u = ed;
while (u != st)
{
edges[p[u]].flow += a[ed];
edges[p[u] ^ 1].flow -= a[ed];
u = edges[p[u]].from;
}
return true;
剩余容量变了，图上多出许多反方向的边，也就是负的cost的边。
: 这边指的cost是指走过arc的cost, 而不是total cost. 这也是理论里面说每个
: iteration需要变化的地方 所以我想是哪里理解错误吧?
你看的文献就不对，要怎么跟你讨论？
但是你说的大致上是正确的，
无论是　最小费用流　还是　最小费用最大流　的SSPA都是如此。
: 另外我还会去看一下 最小费用流 跟 最小费用最大流的差别 ORZ
建议你找英文的资料，因为中文网络上几乎没有人把这件事搞清楚，尤其是竞赛选手。
图论算法强者tarjan有写一本网络流的书，
它里面有稍微提到 minimum cost maximum flow，
可以加减参考看看。
https://books.google.com.tw/books?id=m1rAB3uWwBwC
: 恳请解惑~~
: 谢谢~

剩余容量变了 会影响cost吗? 边一开始就建好了 后面不会增加跟减少了吧?我指的是那篇blog的实作方式.....

本来没有反方向的边，后来有了，也就连带产生-cost他的实作方式是预先都建好反方向的边 用xor 1得到反方向的边 然后一开始就设定好+cost和-cost 所以他其实还是有变只是一开始就把所有变化预先弄好然后每次的最短路径的cost也都通通不一样

saladim 你说的 cost 改变 是指改变 reduced cost 还是？

指的是改变reduced cost...而reduced cost就是会变动到毎根edge的cost ==> Cost' = Cost + Pi(v) - Pi(u)我上面说的是 minmum cost flow的部分, 问题在于minmumcost "max flow" 是否同样适用同样理论? 如果是的话 为何实作里面edge cost并没有变化(在residue graph了)若是两个问题不能用同一理论处理 那就要去找到为什么那样写可以得到minmum cost max flow....所以问题分成两部份啦~~~~

Cost' = Cost + Pi(v) - Pi(u) 这个东西就是把权重调成非负方便实施dijkstra最短路径算法这个技巧在CLRS的johnson's algorithm也有用过前面提到 会有反向边与-cost出现 如果不调整成非负那么只能用floyd-warshall或bellman-ford复杂度较高的方法然后古代的文献 基本上会把这个叫做potential什么什么的而不会介绍他有调成非负权重的功效这个东西是optional的 你有做或没做 都不会影响正确结果时间复杂度差个O(V^2)而已

应该没有差到 V^2 那么多吧.. 感觉 V^2 好大啊..

再研究一下...文中贴出的参考资料调成非负跟reduced cost是两件事情...而且发现这两种问题 其实是有点不一样 只不过是有些引理相同.....有一些本质上差异....ㄟ 等等 再研究一下好惹 @-@

我说错了 差V才对一开始我不知道你讲的 reduced cost 是在讲什么 我用猜的

reduced cost 是 mathematical programming 的概念你可以上 wiki 看解释应用到 shortest path 的问题上时 就变成没负边的图

因为他一开始都没有提到 "reduced cost" 这个词汇

虽然还没全懂 似乎是这样: No negative cycle => Cost'会>=0 ==> 所以可用Dijk所以reduced cost在此变成非负!!又没有negative cycle跟integer cost就有optimal sol. 故得解...虽然就是各位先进所说的 用我的理解走一遍 ORZ其他有提到的再继续看.....@-@||(min cost flow跟 min cost max flow有什么关联还没懂..)

其实 min cost flow 有很多变化形.. 所以很难搞清楚..