基于ford-fulkerson的双向最大流问题

Question

我认为这就像是最大流问题的无向图版本。

所以对于每个边a->b，b->a也是有效的。它是双向的。它们共享相同的容量。这意味着如果我在两个顶点a，b之间有容量10，并且我有一个从a到b的流，成本为5，那么从a到b的剩余容量将是5，以及从b到a的剩余容量。

我的解决方案是让一条有向边从b到a，另一条从a到b。问题是，如果我在残差图中减少a->b的残差，我还会增加后向边b->a的残差吗？

Answer 1

嗯。在每条有可用容量的扩充路径中，如果你在残差图中从a->b中减少残差，你必须增加后向边b->a的残差。这使得流可能会在以后“返回”。