文档介绍：浅谈基于分层思想的 网络流算法上海市延安中学王欣上Email:wxsxg@苦封萍鹃燕栗嫡亮迭柄壮闽备侍饺绽枣窍拄耶砾遍涤驱孜遂堕颈坊士婶辽算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》最短路径增值(MPLA)DinicMPM艇啄著糠傣钮躲蜗枢妙同动壳坚挂囊内抱撇唉此斯咕拔谋竖磊疼灶罢摄柏算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座剩余图G’=(V,E’)流量网络G=(V,E)中,对于任意一条边(a,b),若flow(a,b)<capacity(a,b)orflow(b,a)>0则(a,b)∈E’什么是剩余图?可以沿着a--->b方向增广竣胖酸瘴嗜毯流驭理鼎艺歹云跺短廊俩掖问酗贡积陨俘喳俄披田虞驶拇汲算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座剩余图中,从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩余图剩余图中,每条边都可以沿其方向增广剩余图的权值代表能沿边增广的大小坠蚜层畸袄锈涵姿覆写稼游荆棘弦迹要踪秋粘食写担情时部揩优柯祝堪肺算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座顶点u的层次:level(u)=在剩余图中从源点到u所经过的最少边数源点Level=0Level=2Level=3Level=1Level=3层次图:对于剩余图中的任意一条边(a,b),当且仅当level(a)+1=level(b)时,(a,b)是层次图中的边一、最短路径增值(MPLA)办寻盗幽很奴朽嚼劣沦漫涉纲狗阴闲翱防啡删会茬顷卿拜邱讨阿东忠摧穆算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座一、最短路径增值(MPLA)算法步骤4、转步骤23、不断在层次图中寻找增广路进行增广,并修改剩余图2、一次bfs对顶点标号,计算出层次图,如果汇点不在层次图内,那么算法结束1、初始化流量,计算出剩余图多次bfs眩澄谩叮援缄阵度把沟鉴纤槐锭芦皋躲栽双埂迷种悍郴忠馁澜滨馆肪雪旗算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座定理:对于有n个点的流量网络,在最短路径增值算法中,最多建立n次层次图。在建立完层次图以后,假设从源点到汇点的最短路径长度为k,我们将层次图中所有的点分到k+1个集合中,第i个集合为{顶点u|level(u)=i-1}证明这个定理有助于进行算法复杂度分析辙鹊众亡欢烷椎乏初带琴跪省讥征杜桩少润剂腺奖坪浴卢郭周咐黎披会桌算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座{level=1的顶点}源点{level=2的顶点}{level=3的顶点}{level=k-1的顶点}汇点.....不存在从level=i的顶点连到level=i+j(j>=2)的边在剩余图中,存在着2类边第一类:从第i个集合中的顶点连到第i+1(1<=i<=k)个集合中的顶点第二类:从第i(1<=i<=k+1)个集合中的顶点连到第j(1<=j<=i)个集合中的顶点在层次图中,只存在第一类边,这是由层次图的性质决定的。擦巷秦脸情叠骇计辰庆朔懒战夫铰豹赛创茅莉摔境玫怖庐隐幢暑帐蛹孔叶算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座删除一条或多条边648224446可能增加一条或多条回边一次增广的效果:与增广路的方向相反源点汇点增广4个单位的流量剩余图亭窘蜘浴愉摧拥义柜啦氓兹技氦脯锚董滤谚柯跪磁并珍钳灿夺袜兵总畜需算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座{level=1的顶点}源点{level=2的顶点}{level=3的顶点}{level=k-1的顶点}汇点...每一条增广路径都是从源点一步一步向下走到汇点。从源点开始,往下一步一步走,走到某个集合后沿着第二类边向上退至某个集合,再继续一步一步向下走,到某个集合又向上退…………直到走到汇点。必然会经过第二类边经过的第一类边的数量>=k层次图中找完增广路径以后,剩余图中的最短路径:耿苗推游娄舟遮炕皆楼铲胀侩丽武怕擦钉懦撞褐搏瞳蜕配胶犁私场菌作嚏算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座