java - Ford-Fulkerson 不规则性(多顶点与回流)

Question

到目前为止，我一直在处理顶点之间只有一条有向边的图。对于我用来测试我的实现的所有示例，已经产生了正确的答案。但是，当我使用一个包含顶点的图形时，该顶点的边沿两个方向运行，但是，我没有给出正确的答案。我一直将这种向后运行的边缘视为这两个顶点之间的回流，因为看起来回流和向后运行的不同“管道”最终将是等效的。我的假设错了吗？

Answer 1

假设两条边的容量为 'a' 和 'b' U--[a]-->V 和 V--[b]-->U 等价于单边 U--[a-b]-->V 不正确。假设 a > b，在第一种情况下负流至 -b 是合法的，但在第二种情况下是非法的。

只能将同向边的流量相加。在下图中，添加从 E 到 F 和 F 到 E 的两个相反的管道使它们从图中消失，从而改变了最优解。