<center> 最小割 </center>
什么是最小割?
割掉网络图的一些边,使得之后的顶点分为两部分,即S可以到达的顶点集合和可以到达T的顶点集合,每个边割开都有会产生一个费用;而最小割就是我们使顶点分为两部分的费用和最小的割法。
且我们已经证明最小割等于该网络流图中的最大流。
最小割多用于什么时候?
所有将顶点划分为两个集合且使得费用最小的问题都可以转化为最小割。
那么如何借此最小割呢?
我们可以先求出最大流,以S为起点在残留网络上 DFS,搜索到的点就是包含 S的一部分且我们将之染色,剩余的则是另一部分,而最小割即是连接两部分的所有边.如果一个边的两个顶点的颜色不一样则该边是割边。