网络流模型 · 最大权闭合子图

Linge_Zzzz · 2024-04-25 16:28:01 · 个人记录

定义

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

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

例如，在上图中，\{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。

1. 对于原图中的边，我们保留，并把其容量设为 \inf。(1)

2. 对于每个原图中的点 u：若 w_u>0 则从 S 向 u 连一条容量为 w_u 的边。若 w_u<0 则从 u 向 T 连一条容量为 -w_u 的边。若 w_u=0，我们不管他。（也可以管，但是容量为 0 就相当于没有边）

3. 我们跑出这个网络的最小割，其容量记为 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 的原因也就呼之欲出了：