Ford-Fulkerson と Edmonds-Karp など。アル。ゼロフローから始めて、それ以上増やせなくなるまで増やします。正の容量の場合。ただし、最初のゼロ フローは、正当なフローであり、容量の制約を満たすフローであることが保証されています。
負の容量では、すべてゼロのフロー割り当ては容量の制約を満たさないため、最大フローに拡張できません。
インターネット上で、負の容量を持つ最大フローは 2 つの最大フローの問題として解決できると示唆しているのを読んだことがありますが、その方法を理解することはできませんでした...