java - Ford-Fulkerson 不规则性（多个顶点与回流）

Question

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

Answer 1

U--[a]-->V具有容量“a”和“b”的两条边V--[b]-->U等效于一条边的假设 U--[a-b]-->V是不正确的。假设 a > b，负流到 -b 在第一种情况下是合法的，但在第二种情况下是非法的。

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