记录一下一些常见的小结论.
最大权闭合子图
在有向图中,每一个点都有一个权值.
选择一个权值和最大的子图,使得每个点的后继都在子图里面,这个子图就叫最大权闭合子图.
从源点 $S$ 向每个正权点连一条容量为权值的边,从每个负权点向汇点 $T$ 连一条容量为权值的绝对值的边.
有向图原来的边容量全部为无限大.
原图的最大权闭合子图的权值就等于所有正权点的权值之和减去新图的最小割.
无源汇上下界可行流
一条边记做 $(u,v,mi,mx)$ ,表示这条边从 $u$ 连向 $v$ ,流量下界和上界分别为 $mi$ 和 $mx$ .
每条边强制流下界,就转化成了 $(u,v,0,mx-mi)$ .
此时会有流量不平衡的点,新建超级源点 $SS$ 与超级汇点 $TT$ .
若某个点 $x$ 流入的流量比流出的流量多 $w$ ,就新建边 $(SS,x,0,w)$ .
否则,若流出的流量比流入的流量多 $w$ ,就新建边 $(x,TT,0,w)$ .
跑一次从 $SS$ 到 $TT$ 的最大流,若 $SS$ 所有的出边都满流,则原图存在可行流.
有源汇上下界可行流
记源点为 $S$ ,汇点为 $T$ .
有源汇和无源汇的区别在于,有源汇的可行流中, $S$ 和 $T$ 两个点可以不满足流量平衡.
我们加一条边 $(T,S,0,\inf)$ ,这样 $S$ 和 $T$ 也流量平衡了,就转化为了无源汇上下界可行流,套用即可.
若存在可行流,那么原图可行流的流量就是 $(T,S,0,\inf)$ 这条边上的流量.
有源汇上下界最大流
先用有源汇上下界可行流的方法求出一个可行流.
若存在可行流,删掉 $(T,S,0,\inf)$ 这条边,在可行流的基础上求出 $S$ 到 $T$ 的最大流,即,不清空已有的流量.
答案就是可行流 + 最大流.
有源汇上下界最小流
先用有源汇上下界可行流的方法求出一个可行流.
若存在可行流,删掉 $(T,S,0,\inf)$ 这条边,在可行流的基础上求出 $T$ 到 $S$ 的最大流.
答案就是可行流 - 最大流.