最小割学习笔记

发表于 2023-09-03

简要的介绍最小割与最大权闭合子图

最小割的概念

使得源点无法到达汇点所需要删除的边集的容量和。

根据最小割最大流定理，可用最大流算法求出最小割的值。

在残余网络中，从源点出发DFS，凡是能通过剩余流量大于0的边到达的点属于S集合，其余点属于T集合，则S集合到T集合之间的边就是组成最小割的边集。

最小割是一种选择，因此可以解决一些最大收益/最小开销类的选择方法。

如：P1361

当然，难点依然是网络流的建图。

若从一个图中选择一个子图，使得每个点的后继都在子图中，则该子图是一个闭合子图。

最大权闭合子图即点权和最大的一个闭合子图。

从源点向所有正点连容量为该正点权值的边，从所有负点向汇点连容量为该负点权值绝对值的边，将图中其他边的容量设为INF，跑最小割。不难证明，所有正点的权值和减去最小割即是最大权闭合子图的权值和。

比如：P4174