Ford-Fulkerson 和 Edmonds-Karp 等。人。从零流量开始并增加它，直到它不能再增加。在正容量的情况下；但是，保证初始零流量既是合法流量，又是满足容量约束的流量。
对于负容量，全零的流量分配将无法满足容量约束，因此无法将其扩充为最大流量。
我在互联网上读到有人建议，负容量的最大流量可以作为两个最大流量问题来解决，但一直无法弄清楚如何去做......
问问题
2182 次
1 回答
1
假设你在从u到v的边上有一个容量限制为 -3，这是什么意思？
好吧，根据定义，这意味着您不能将超过 -3 个单位的流量从u推到v；表示从u到v的流量可以是例如 -5、-4 或 -3。如果我们通常假设-x从u到v的流与x从v到u的流相同，那么我们会看到这些 -5 或 -4 或 -3 的示例流将转换为 5 或从v到u的流量为4 或 3 ，此外，从v到u的流量不能小于 3。
因此，我们看到 - x从u到v的最大容量等价于x从v到u的最小容量约束，因此在最大流计算中处理负容量约束的问题减少为同时处理最大和最小正的问题- 仅容量。
可以通过首先在图上找到可行流来处理最小和最大容量，该流满足流规则和容量约束，但不一定是最大流——这可以通过在特殊构造的“循环”上找到图从原始图导出，然后通过解决最大流问题将可行流变成最大流。此技术在以下链接中详细讨论：最大流量幻灯片
于 2019-05-22T16:52:39.363 回答