上下界网络流小结

常用的几种:

有/无源汇可行流

有/无源汇费用流

有源汇最大/最小流


有/无源汇可行流:

首先,我们的算法是基于无源汇,若是有源汇的话,我们从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