网络流小记

最大权闭合子图

给出一张有向图，每个点有点权，要求若选出一个点，则必须选择其能到达的点，求权值和最大的子图。

解法

将点划分为两个点集，\(V_1\) 表示正权点，\(V_2\) 表示负权点，设起点为 \(S\)，终点为 \(T\)。

\(S\) 向 \(V_1\) 内的点连流量为点权的边，\(V_2\) 向 \(T\) 内的点连流量为点权的相反数的边，原图中的边保留，流量为 \(+\infty\)。

答案即为正点权总和减新图的最小割。

证明

考虑最小割的意义，\(S\) 连向的边断掉，表示不选某个正权的点，连向 \(T\) 的边断掉，表示选择某个负权的点。

这样的话最小割相当于是不选的正权点的权值和减选择的负权点的权值和。

正点权总和减新图的最小割自然就是答案。

求方案

从 \(S\) 出发，走残余流量大于 \(0\) 的边，遇到的点集就是选择的正权点。