最小费用可行流

考虑一张网络流图,每条边定义为(u,v,w,l,r),代表从u到v的一条有向边,费用为w,容量为[l,r]闭区间,源点s汇点t已知,且保证源点没有入边、汇点没有出边
同时定义常规费用流图的边为(u,v,w,cap)
现在我们需要求这张图的最小费用可行流(就是满足所有边的流量上下限制,同时费用最小)
按照如下方式建立附加边和附加点:
1.建立附加源点SS,和附加汇点TT
2.对于原图中每一个点(包括源汇)u,令d[u]代表u点的所有入边的流量下界减去出边的流量下界
2.1.如果d[u]是负数,那么从u连一条边(u,TT,0,-d[u])到TT
2.2.如果d[u]是正数,那么从SS连一条边(SS,u,0,d[u])到u
3.对于原图中每一条边(u,v,w,l,r),连边(u,v,w,r-l)
4.连边(t,s,0,inf)(注意这里是原图的源汇点!不是附加的源汇点!!)
这样以后,从SS到TT跑新图的最小费用最大流,再加上原图中每条边的下界流量乘以费用(必须跑的部分),就是最小费用可行流的费用了

为什么?
我们考虑一个点,流入边流量下界比流出边流量下界大1,即d[u]==1
此时,我们要有一个“补流”的思想
此时出小于入,那么出边的流量下界就会比入边的小1
因为下界一定是要满的,而我们如果希望消除下界影响,新图中的旧图的边,流量上届一定是(r-l)
那我们势必要找一个方法,令这个比较小的流量流出下界,能与比较大的流量流入下界“平起平坐”
这个时候,假如我们从超级源补1的流量过来,那是不是相当于“帮了”输出边一把,平衡了一下“实力强大”的输入边呢?
这样我们就完成了补流过程

如果最大流的大小等于ss出发的所有边的流量上限之和,则存在这样的附加流满足题意

原文地址:https://www.cnblogs.com/smashfun/p/13259192.html