最大权闭合子图

闭合图

若对于 \(\forall x \in G\) ，都有点 \(x\) 的所有后继点都在有向图 \(G\) 内，则称 \(G\) 为闭合图。

最大权闭合子图

将带权有向图 \(G\) 的所有是闭合图的子图中权值最大的称为最大权闭合子图。

最大流求最大权闭合子图

构建超级源点 \(s\) 和超级汇点 \(t\) ，将权值为正的点与源点相连，权值为负的点与汇点相连，边的流量为点的权值的绝对值；原图的边流量为 \(inf\) 。

可以将该图关于 \(s-t\) 的最大流理解作“最少损失的权值”。显然一个正权点的贡献只会受其后继负权点的影响，则其损失为后继点的流量；若其权值小于其后继负权点的权值绝对值之和，即该点中无残余流量，该点流出的流量即为其权值，等价于没有选择这个点。

则原图最大权闭合子图的权值为权值为正的点的权值之和减去最大流。