最小割问题
作者: 人间温柔 , 2023-01-25 21:35:25 , 所有人可见 , 阅读 31
学习笔记目录
有任何问题,欢迎私信/评论.
码字不易,求点赞啦~
根据我在 网络流的基本概念 中提出的概念,最小割就应该是所有割中,流量最小的一个.题目通常求的是最小割的容量.
有一个非常神奇的定理:最大流最小割定理,这个定理只有短短的几个字:最大流等于最小割.
关于定理的证明,其实我没太看懂,但我个人的直观理解就是:最小割限制了整个网络的流的上界,所以就有最大流等于最小割.
因此,求解最小割就变得很简单了,只需要套用最大流的 $dinic$ 算法就可以求解了.