网络流杂笔记

最大权闭合子图：

一张有向图中每个点都有点权，边\((u,v)\)代表如果选择了\(u\)就必须选择\(v\)，求最大化总权值。

化为网络流建模，可以对于所有权值为正的点（包括0），连接\((s,u,val_u)\)，否则连\((u,t,-val_u)\),对于图内部的边就连\((u,v,\infty)\)。

答案就是\(正权点总和-最大流\)，方案构造即割完后（即去掉剩余容量为\(0\)的点）选\(S\)集中的点。

注意到最大权闭合子图可以解决如下问题

上下界流：

分为无源汇上下界流和有源汇上下流。