最大权闭合子图模型

写了几道这类题，觉得很有意思，有必要总结一下

什么是闭合子图？

对于一个有向无环图，它的一个闭合子图满足对于其中的任意一个点，从它出发能够到达的所有点都和它在同一个闭合子图中

比如下面这个图

它的所有闭合子图集合为：
$\emptyset,\{3\},\{5\},\{4,5\},\{3,4,5\},\{2,3,4,5\},\{1,2,3,4,5\}$

其实就是走不到集合外的点，“闭合”的子图
——GoldenPotato

什么是最大权闭合子图？

对于一个点带正/负权的有向无环图，其最大权闭合子图在所有的闭合子图中，点权和最大

怎样用到题目中？

建立超级源点 $s$ 和超级汇点 $t$ ，从 $s$ 向所有点权为正的点连边，边权为点权;从所有点权为负的点向 $t$ 连边，边权为点权的相反数;原图中原本就存在的边之边权设为正无穷

那么最大权闭合子图的权值等于所有正权点之和减去最小割

证明：

以下引自https://www.cnblogs.com/TreeDream/p/5942354.html
字母比较多，请注意辨别和理解

首先我们要证明两个引理：
1.最小割一定是简单割
简单割指得是：割 $(S,T)$ 中每一条割边都与 $s$ 或者 $t$ 关联，这样的割叫做简单割。
因为在图中将所有与 $s$ 相连的点放入割集就可以得到一个割，且这个割不为正无穷。而最小割一定小于等于这个割，所以最小割一定不包含无穷大的边。因此最小割一定一个简单割。
2.简单割一定和一个闭合子图对应
闭合子图 $V$ 和源点 $s$ 构成 $S$ 集，其余点和汇点 $t$ 构成 $T$ 集。
首先证明闭合子图是简单割：若闭合子图对应的割 $(S,T)$ 不是简单割，则存在一条边 $(u,v),u∈S,v∈T$ ，且c(u,v)= $∞$ 。说明 $u$ 的后续节点 $v$ 不在 $S$ 中，产生矛盾。
接着证明简单割是闭合子图：对于 $V$ 中任意一个点 $u$ ， $u∈S$ 。 $u$ 的任意一条出边 $c(u,v)=∞$ ，不会在简单割的割边集中，因此 $v$ 不属于 $T$ ， $v∈S$ 。所以 $V$ 的所有点均在 $S$ 中，因此 $S-s$ 是闭合子图。
由上面两个引理可以知道，最小割也对应了一个闭合子图，接下来证明最小割就是最大权的闭合子图。
首先有割的容量 $C(S,T)=T$ 中所有正权点的权值之和 $+S$ 中所有负权点的权值绝对值之和。
闭合子图的权值 $W=S$ 中所有正权点的权值之和 $-S$ 中所有负权点的权值绝对值之和。
则有 $C(S,T)+W=T$ 中所有正权点的权值之和 $+S$ 中所有正权点的权值之和=所有正权点的权值之和。
所以 $W=$ 所有正权点的权值之和 $-C(S,T)$
由于所有正权点的权值之和是一个定值，那么割的容量越小， $W$ 也就越大。因此当 $C(S,T)$ 取最小割时， $W$ 也就达到了最大权。