问最大流-最小割集定理EN
最编程
2024-07-31 20:30:42
...
我理解Ford-Fulkerson求最大流的方法,但我很难理解min如何给出最大流的值。
最大流-最小切割定理指出,从源到汇的最大流量等于最小切割的值。
CLRS中的Min定义为:
网络的最小割集是指其容量比网络的所有割集都最小的割集。
如果容量最小,就意味着存在容量较高的增强路径,那么为什么容量较低的路径会出现最大流量?作者所说的容量是指residual capacity
吗?因为这一切都有意义。
上一篇: Acwing 2326: 至尊剑(求解最小割下的最大权独立集) - 建议保存
下一篇: 最小点割集