最大权闭合子图

Preface

这东西一看就跟网络流之类的有关系。。。

Text

首先，闭合子图就是就是在有向图中，这个子图中的点的所有出边指向的点，都在这个子图中。

闭合子图有

{1,2,3,4,5}

{3,4,5},{2,4,5}

{4,5},{5}

顾名思义，最大权闭合子图就是点权最大的闭合子图
例子中为{3,4,5}

那么最大权闭合子图的权和怎么求呢？

大家有空可以看一看 胡伯涛《最小割模型在信息学竞赛中的应用》

我们先构造一个网络

新建源点S,汇点T

将S向所有权值为正的点连一条容量为权值的边
将所有权值为负的点向T连一条容量为权值的绝对值的边
原图中的边容量为正无穷

结论就是，最小割将整个网络分成两个点集合（一个是S能到的，一个是能到T的），S所在的集合（除去S）即为最大权闭合子图。

怎么推导呢？

定义简单割为只包含连着S,T的边的割

首先，最小割一定是简单割
十分显然。因为除了这些边，其他边都是正无穷

我们将刚刚的图建成网络

然后我们来证明上面的结论

设S所在集合为S1,T所在集合为S2

显然S1一定是一个闭合子图

设P为一个简单割的容量
易得P=S1中权值为负的点权绝对值和（设为FS1）+S2中权值为正的点权和（设为ZS2）

P=FS1+ZS2

设T为一个闭合子图的点权和
易得T=S1中权值为正的点权和（设为ZS1）-FS1

那么P+T=ZS1+ZS2=所有权值为正的点权和

因为这个东西是定值，所以如果我们希望T最大，那么P最小，所以就是最小割

所以Tmax=所有权值为正的点权和−Pmin

然后就可以跑最大流了