定义

我们先来定义什么是闭合子图。

通俗地讲，在一个有向图中，我们选择一些点作为一个点集。若这个点集中任何一个点所能到达的所有点都在这个点集中，我们称这个点集是一个闭合子图。

例如，在上图中，$\{5\},\{2,3,4,5\},\{1,2,3,4,5\}$ 都是这个图的闭合子图。而 $\{2,4,5\}$ 则不是，因为 $3$ 可以到达 $4$，而 $4$ 不在这个点集中。

现在，每个点有一个点权 $w_i$，$w_i$ 可以是负数，我们要选择一个最大权闭合子图 $S$ 来最大化 $\sum_{u\in S}w_u$，即选择一个点权和最大的闭合子图。

建模方法

我们考虑把它转化成网络流中的最小割来解决。

具体地，建立超级源点 $S$ 和超级汇点 $T$。

对于原图中的边，我们保留，并把其容量设为 $\inf$。
对于每个原图中的点 $u$：若 $w_u>0$ 则从 $S$ 向 $u$ 连一条容量为 $w_u$ 的边。若 $w_u<0$ 则从 $u$ 向 $T$ 连一条容量为 $-w_u$ 的边。若 $w_u=0$，我们不管他。（也可以管，但是容量为 $0$ 就相当于没有边）
我们跑出这个网络的最小割，其容量记为 $c$，则最大权闭合子图的权值和就是 $\sum_{w_u>0}w_u-c$。

正确性

首先，最小割一定不会割掉原图中的边，因为这些边的容量是 $\inf$，割掉它还不如把其它所有边割掉。

其次，我们是不会主动选择一个负权点 $u$ 的。若选择了这个点，则其在原图中所有能到达的点都被选择了，那还不如选择 $u$ 的所有儿子而不选择 $u$ 更优。

如果我们割掉了一条从 $S$ 到正权点 $u$ 的边，则说明我们不选择 $u$。

如果我们割掉了一条从负权点 $v$ 到 $T$ 的边，则说明我们选择 $v$。

每个点都只有选或者不选两种情况，所以，一个割一定对应一个子图。

对于一条从 $S$ 连向正权点 $u$ 的边，若不割掉它，则说明我们选择了原图中 $u$ 这个点，进而选择了 $u$ 的所有能到达的点 $V$。$V$ 中如果有负权点，那么必须割掉这些负权点到 $T$ 的边（也即选择这些负权点），否则存在从 $S$ 到 $T$ 的路径，不能形成一个割。

所以，一个割一定对应一个闭合子图。

对于一条从 $S$ 连向正权点 $u$ 的边，若不割掉它，则说明我们选择了原图中 $u$ 这个点，进而选择了 $u$ 的所有能到达的点 $V$。$V$ 中如果有正权点，则 $S$ 到这些点的边一定不会割掉（对应着我们选择了这些点），因为在割掉 $V$ 中所有负权点到 $T$ 的边的前提下，这些点不用割掉任何其它的负权点到 $T$ 的边，因此不割肯定比割了要更优。

若对于一个负权点 $v$，其所有的前驱正权点到 $S$ 的边都被割掉了，那么就不用割掉 $v$ 到 $T$ 的边了，因为显然没有任何点能选择 $v$。

以上的这些只是为了加深理解，最小割一定对应最大权闭合子图。

最后，答案是 $\sum_{w_u>0}w_u-c$ 的原因也就呼之欲出了：

$c$ 中包含了 $S$ 到正权点的边的容量，即不选这个正权点，所以肯定要从正权点的和中减去。

同时它又包含了负权点到 $T$ 中的容量，即选择这个负权点，因为权值是负的，所以肯定要减去。（与前文 $w_u<0$ 时边的容量设成 $-w_u$ 形成呼应）

关于具体方案，根据上文所说的割不割与选不选的关系可以轻松求得。

$$Q.E.D.$$