-图论与算法-第九讲 最小费用流

《-图论与算法-第九讲 最小费用流》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法艺术与信息学竞赛》算法图论第九讲最小费用流声明本系列教学幻灯片属于刘汝佳、黄亮著《算法艺术与信息学竞赛》配套幻灯片本幻灯片可从本书blog上免费下载，即使您并未购买本书.若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用有任何意见，欢迎在blog上评论Blog地址：http://artofalgo.blogchina.com内容介绍一、最小费用流问题二、消圈算法三、网络单纯形法四、应用举例一、最小费用流问题问题描述如果给流网络的每条弧新加一个权cost(u,v),代表单位流量

2、的费用,则总费用为每条弧的f(u,v)*cost(u,v)之和以下三个流流量相同,但中图的费用最小分布网络分布网络(distributionnetwork):带弧容量、费用和点权(supply或demand)的网络定理:分布网络最小费用可行流问题等价于s-t网络最小费用最大流问题以后未加说明,我们只考虑分布网络的最小费用可行流问题,简称最小费用流问题(mincostflowproblem)残量网络设(u,v)的容量为c,流量为f,费用为x若f>0,Gf中存在弧(v,u),容量为f,费用为x若f

3、量为c-f,费用为-x因为有负费用,所以有可能有负费用圈定理:流f是相同流量的流中费用最小的流当且仅当Gf不存在负费用圈必要性.若存在负费用圈,沿它增广将得到相同流量费用更小的流充分性.不存在负费用圈,却有更小费用流为f’,则f’-f是循环流,可分解为圈的并,但这些圈费用为正二、消圈算法算法思想消圈算法:先求最大流,再在Gf中寻找负费用圈并沿它增广改进:增加附加弧(s,t),费用大于s-t最大费用路(如VC),弧上的初始流大于s-t最大流(如s出发的弧容量和加1)消圈算法将让尽量多的流移出附加弧,因此得到的流是最大流.最后附

4、加弧可能有余量,应当忽略实际效果:最小费用增广路算法,因为Gf中任何s-t路和t-s一定构成负费用圈分析最坏情况分析:每次找负费用圈O(VE),每次只把费用更新1,一共需要ECM次(M为最大费用,C为容量),在稀疏图中总时间复杂度为O(VE2CM)=O(V3CM)改进方向每次不重新找圈,而是从中间状态找每次不随意找圈,而是只找满足某些条件的圈存在消圈算法,一共只找O(VE)个圈三、网络单纯形法算法思想思想:维护可行树,并使用重加权技术加速负圈寻找并减少迭代次数弧的三种状态:空(empty),满(full),部分(partia

5、l),Gf中分别只有u-v,只有v-u和都有若部分弧不形成环,则可行树是网络中包含所有部分弧的任意生成树.忽略弧的方向.注意部分弧代表正反向弧都在Gf中的弧构造可行树方法一:求最大流.若部分弧形成圈,沿圈增广填满一些弧,再加入满弧或空弧,构成可行树构造可行树方法二:附加弧(s,t),容量和费用都很大,则求出最大流后,只有(s,t)是部分弧,在剩下图中任意构造一棵生成树,加入(s,t)即可算法思想可行树:由于可行弧在Gf中都是双向的,任意再加一条弧一定可以形成一个圈.思想:快速找到加入哪一条弧得到的圈为负顶点势(vertexp

6、otential)方法:给每个顶点u赋予顶点势phi[u]解释:phi[u]为在结点u买流的费用简化费用(reducedcost)公式:c*(u,v)=c(u,v)-(phi[u]-phi[v])解释:从结点u买流以后运到v后卖掉简化费用可以即需即算,无需存储顶点势如果顶点势让可行树所有边的简化费用为0,称顶点势是有效的(valid).定理:所有有效顶点势相差一个常数.可任意指定一个点为树根,势为0,其他可以算出合格弧称一条弧是合格(eligible)的,如果它和可行树构成了一个负费用圈定理:一条弧是合格的当且仅当它是满弧,

7、且有正简化费用,或它是空弧,且有负简化费用证明:把圈上所有弧的简化费用等式叠加,则费用和=非树边的简化费用定理:若不存在合格弧,得到最小费用流可行树的维护若找到合格边,则沿负费用圈增广