上下界网络流小结

常用的几种：

有/无源汇可行流

有/无源汇费用流

有源汇最大/最小流

有/无源汇可行流：

首先，我们的算法是基于无源汇，若是有源汇的话，我们从T向S连一条INF边使得图变成无源汇。注意此时S,T看成普通点。

无源汇可行流：

记录每一个点的入度in和出度out，A[i]=out-in即我们需要平衡的流量。

if A[i]>0 add(S,i,A[i]);

if A[i]<0 add(i,T,-A[i]);

同时，原图中的[x,y,L,R]边变成add(x,y,R-L)。

跑S-T的最大流（新的ST）。

若$MC==\sum_iA[i]$则有解，否则无解。

此时一组可行解为每条边的流量=L[i]+a[i].w（新建图中）。

感性证明：

对于一个点的所有入度，不论其怎么来，最终效果等同于到达这个点。我们用一个代表点S来处理所有这样的边即可，这样每一个点都会得到跟原图下界一样多的流量。

对于一个点的所有出度，不论其去哪里，最终效果等同于离开这个点。我们用一个代表点T来处理所有这样的边即可，这样每一个点都会流出跟原图下界一样多的流量。

这样我们建边就有逻辑可寻了。

有/无源汇费用流

与之前的那个如出一辙，就是把DINIC换成MCMF即可。

有源汇最大/最小流


1.我们用可行流的算法得到一组可行解。

2.删除图中的新加入的边（若是有源汇不要忘了(T,S,INF)）。

3.判断是否合法。不合法直接return；

4.ans赋值为e[tot].w。此时e[tot].w为（T,S,INF)边的反边的流量。

最大流=ans+从OS->OT的最大流

最小流=ans-从OT->OS的最大流

（图中的OS-OT跑最大流相当于再增广出尽可能多的流）

（图中的OT-OS对应的是反向边，跑最大流相当于退掉尽量多的流）

上下界网络流小结

原文：https://www.cnblogs.com/wuzewen/p/11135628.html