网络流与匹配问题最大流,最》ppt课件.ppt

《网络流与匹配问题最大流,最》ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、网络流与匹配问题——最大流，最小费用最大流，最大匹配，最佳匹配李子星概念与定义对于一个有向图G0=(V,E)，若其中的每条边有一个非负实数值cuv表示这条边的容量（对于不在图中的边定义cuv=0），且图中有一个源点s和一个汇点t，且s<>t，那么可以称这个图为网络图，记为G1=(V,E,c,s,t)。对于网络图G1=(V,E,c,s,t)，若对任意的u和v属于V且u<>v，都有一个非负实数值fuv表示边上的流量，且满足条件：对任意的u和v属于V，有fuv<=cuv

2、，fuv=-fvu对任意的u属于V且u<>s且u<>t，有sum{fuv

3、v属于V}=0那么可以称f为图G1的一个可行流。概念与定义对于网络图G1=(V,E,c,s,t)的一个它的可行流f，定义sum{fsv

4、v属于V}为f的流量。若f的流量为0，那么称f为一个零流。对于网络图G1=(V,E,c,s,t)，其流量最大的可行流可以称为G1的最大流。对于网络图G1=(V,E,c,s,t)和它的一个可行流f，若G2=(V,E,c’,s,t)满足：对任意的u和v属于V都有c’uv=cuv-fuv那么称G

5、2为G1对可行流f的残量网络。概念与定义对于网络图G1和可行流f的残量网络G2=(V,E,c’,s,t)上的任意一条s到t的路径p=，uf(p)=min{c’vi-1vi

6、1<=i<=k}可以称为这条路径的可改进量。对于网络图G1和流量f的残量网络G2上的任意一条s到t的路径p，若uf(p)>0，那么称p为G2上的一条增广路。概念与定义由G2上的一条增广路p=，可以得到G1的一个可行流f(p)：对任意的u和v属于V且不属于

7、p，f(p)uv=0对任意的0

8、残量网络G2若G2上存在s到t的增广路p，则合并f和f(p)为新的f否则跳出循环最大流求G2上s到t的路径p的方法可以随便用，深搜广搜都可以，肯定最多遍历每条边一次，因此找一次增广路的时间复杂度为O(

9、E

10、)。总的时间复杂度为O(D*

11、E

12、)，D为找增广路的次数。最大流的Dinic算法计算残量网络忽略c为0的边后的层次图在残量网络中只保留i层指向i+1层的有向边的情况下，找到所有存在的增广路并合并至可行流中Dinic算法与层次图i号节点的层次level[i]：从s点到i号节点最少要经过的边数，一

13、轮广搜在O(

14、E

15、)的时间复杂度内就能得到。源点Level=0Level=2Level=3Level=1Level=3Dinic算法的多路增广得到残量网络的层次图后，我们只考虑其中第i层指向i+1层的有向边。funcFindPath(u,uf:int):intif(u=t)result:=ufelseuf’:=0;foreachvwhere(c[u,v]>0&&level[v]=level[u]+1&&uf’

16、]-=tuf;　c[v,u]+=tuf//合并流uf’+=tuf;if(uf’=0)level[u]:=-1;//u根本就没有到t的路径，以后也不用来了result:=uf’uf是当前得到的s到u的路径的可改进量，返回值是从u到t的所有路径的可改进量的和与uf的较小值。uf‘是已经找到的u到t的路径的可改进量的和。可行流的合并是这段代码最难理解的地方。Dinic算法的多路增广这个多路增广的效率如何？每找到一条增广路，至少会有一条边被删除，因此最多找

17、E

18、条增广路。每条增广路长度一定不超过

19、V

20、。

21、一轮多路增广的时间复杂度就是O(

22、V

23、*

24、E

25、)Dinic算法的多路增广经过一轮多路增广后，一定至少出现一个“断层”，即存在某一层，这一层没有指向下一层的边。那么重新求得的层次图的层数一定会增加，而层数最多就

26、V

27、层。所以Dinic算法的总的时间复杂度为O(

28、V

29、2

30、E

31、)，但实际运行效果非常好，对于节点数万个，边数达十万条级别的图，都能很快的出解。是传说中效率最高的最大流算法。NOI2006最大获利题意：有n个可能的中转站，建造它需要花费P[i]，有m个用户群，当A[i]和B[i]两个中转站都