有一个有向图，每一个点都有一个权值（可以为正或负或$0$），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。
如下图：
能选的子图有$Ø$(即不选),{$4$},{$3,4$},{$2,4$},{$1,2,3,4$},它们的权值分别为$0,-1,5,-6,4.$
所以最大权闭合子图为{$3,4$}，权值为$5$.
解法
这个问题可以转化为最小割问题，用网络流解决。
从源点$s$向每个正权点连一条容量为权值的边，每个负权点向汇点$t$连一条容量为权值的绝对值的边，有向图原来的边容量全部为无限大。
求它的最小割，割掉后，与源点s连通的点构成最大权闭合子图，权值为（正权值之和$-$最小割）。
如何理解
割掉一条边的含义
由于原图的边都是无穷大，那么割边一定是与源点$s$或汇点$t$相连的。
割掉$s$与$i$的边，表示不选择$i$点作为子图的点；
割掉$i$与$t$的边，表示选择$i$点为子图的点。
如果$s$与$i$有边，表示$i$存在子图中；
如果$i$与$t$有边，表示$i$不存在于子图中。
合法性
只有$s$与$t$不连通时，才能得到闭合子图。
如果$s$与$t$连通，则存在点$i,j$，使得$s$到$i$有边，$i$到$j$连通,$j$到$t$有边，所以$j$一定是$i$的后继，但选择了$i$，没有选择$j$，不是闭合子图。
如果$s$与$t$不连通，选择了正权点$i$，一定选择了$i$后继中的所有负权点。设$j$是$i$的后继中的正权点，则割掉$s$到$j$的边是没有意义的，最小割不会割掉它，则$j$一点被选中，所以$i$的所有后继都被选中，符合闭合图的定义。
最优性
最小割=(不选的正权之和+要选的负权绝对值之和）
最大权闭合子图=（正权之和-不选的正权之和-要选的负权绝对值之和）=正权值和-最小割
因为正权值和，是定值，而最小割保证值最小，所以最大权闭合子图一定最优。
例题
拓展
要求输出方案
枚举每个点的$dep$，如果$dep<inf$，那么则是方案内的点
因为那种无论怎么买花费$>$收入，这样的购买有一个特点，因为它不能供给需求，所以源点到它的残流一定是$0$，就是说不管是正向边还是反向边都是$0$，同样的那些可以供给的，源点到它的残留一定大于$0$，也就是正向边或者反向边大于$0$，说明做这个购买能赚钱。
所以在最后一遍$bfs$时，边权为$0$的边是不会走的，也就是说$bfs$时只会走边权大于$0$的边，所以走过的每一个点都是方案中的点，因为只有走过的点$dep$才会小于$inf$，所以只需要找出$dep<inf$的点即可