作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 最大流最小费用问题
时间Sun Mar 29 10:11:35 2015
※ 引述《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
: 恳请解惑~~
: 谢谢~
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.80.89
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1427595099.A.01F.html
1F：→ saladim: 剩余容量变了 会影响cost吗? 边一开始就建好了 後面不会 03/29 21:25
2F：→ saladim: 增加跟减少了吧? 03/29 21:25
3F：→ saladim: 我指的是那篇blog的实作方式..... 03/29 21:27
4F：→ DJWS: 本来没有反方向的边，後来有了，也就连带产生-cost 03/29 23:16
5F：→ DJWS: 他的实作方式是预先都建好反方向的边 用xor 1得到反方向的 03/29 23:17
6F：→ DJWS: 边 然後一开始就设定好+cost和-cost 所以他其实还是有变 03/29 23:18
7F：→ DJWS: 只是一开始就把所有变化预先弄好 03/29 23:18
8F：→ DJWS: 然後每次的最短路径的cost也都通通不一样 03/29 23:19
9F：推 FRAXIS: saladim 你说的 cost 改变 是指改变 reduced cost 还是？ 03/30 06:24
10F：→ saladim: 指的是改变reduced cost...而reduced cost就是会变动到 03/30 09:12
11F：→ saladim: 毎根edge的cost ==> Cost' = Cost + Pi(v) - Pi(u) 03/30 09:13
12F：→ saladim: 我上面说的是 minmum cost flow的部分, 问题在於minmum 03/30 09:14
13F：→ saladim: cost "max flow" 是否同样适用同样理论? 如果是的话 为 03/30 09:15
14F：→ saladim: 何实作里面edge cost并没有变化(在residue graph了) 03/30 09:16
15F：→ saladim: 若是两个问题不能用同一理论处理 那就要去找到为什麽那 03/30 09:17
16F：→ saladim: 样写可以得到minmum cost max flow....所以问题分成两部 03/30 09:18
17F：→ saladim: 份啦~~~~ 03/30 09:18
18F：→ DJWS: Cost' = Cost + Pi(v) - Pi(u) 这个东西就是把权重调成非负 03/30 09:22
19F：→ DJWS: 方便实施dijkstra最短路径演算法 03/30 09:22
20F：→ DJWS: 这个技巧在CLRS的johnson's algorithm也有用过 03/30 09:22
21F：→ DJWS: 前面提到 会有反向边与-cost出现 如果不调整成非负 03/30 09:23
22F：→ DJWS: 那麽只能用floyd-warshall或bellman-ford复杂度较高的方法 03/30 09:24
23F：→ DJWS: 然後古代的文献 基本上会把这个叫做potential什麽什麽的 03/30 09:25
24F：→ DJWS: 而不会介绍他有调成非负权重的功效 03/30 09:25
25F：→ DJWS: 这个东西是optional的 你有做或没做 都不会影响正确结果 03/30 09:28
26F：→ DJWS: 时间复杂度差个O(V^2)而已 03/30 09:29
27F：推 FRAXIS: 应该没有差到 V^2 那麽多吧.. 感觉 V^2 好大啊.. 03/30 21:45
28F：→ saladim: 再研究一下...文中贴出的参考资料调成非负跟reduced cost 03/31 00:02
29F：→ saladim: 是两件事情...而且发现这两种问题 其实是有点不一样 只 03/31 00:03
30F：→ saladim: 不过是有些引理相同.....有一些本质上差异.... 03/31 00:03
31F：→ saladim: ㄟ 等等 再研究一下好惹 @-@ 03/31 00:05
32F：→ DJWS: 我说错了 差V才对 03/31 08:52
33F：→ DJWS: 一开始我不知道你讲的 reduced cost 是在讲什麽 我用猜的 03/31 08:54
34F：推 FRAXIS: reduced cost 是 mathematical programming 的概念 03/31 20:08
35F：→ FRAXIS: 你可以上 wiki 看解释 03/31 20:08
36F：→ FRAXIS: 应用到 shortest path 的问题上时 就变成没负边的图 03/31 20:09
37F：→ DJWS: 因为他一开始都没有提到 "reduced cost" 这个词汇 04/01 09:02
38F：→ saladim: 虽然还没全懂 似乎是这样: No negative cycle => Cost'会 04/02 15:25
39F：→ saladim: >=0 ==> 所以可用Dijk所以reduced cost在此变成非负!! 04/02 15:26
40F：→ saladim: 又没有negative cycle跟integer cost就有optimal sol. 故 04/02 15:27
41F：→ saladim: 得解...虽然就是各位先进所说的 用我的理解走一遍 ORZ 04/02 15:28
42F：→ saladim: 其他有提到的再继续看.....@-@|| 04/02 15:28
43F：→ saladim: (min cost flow跟 min cost max flow有什麽关联还没懂..) 04/02 15:30
44F：推 FRAXIS: 其实 min cost flow 有很多变化形.. 所以很难搞清楚.. 04/02 22:38