登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

最大流和二分匹配  

2008-12-09 20:47:20|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/7097176720081198472074/

二分图,是图论中的一个经典模型,关于二分图,涉及了很多问题,比如最大匹配,最优匹配,完美匹配,最小覆盖。网络流也是这样,再求最大匹配的时候,实际上可以利用转化的思路,就像利用最短路算法求解差分约束系统,利用单源最短路求单目标最短路,利用单源最大流求多源最大流,都是利用了转换的思想,将一个不熟悉的问题转换或者规约为一个熟知的问题。

再比如如果可以把很多问题可以规约到最大流,便可以证明该问题存在多项式时间算法。

对于二分图最大匹配,经典的算法是匈牙利算法,主要利用增广路求最大匹配。 

详细介绍请参考: 

http://imlazy.ycool.com/post.1603708.html

http://hi.baidu.com/deking/blog/item/74c61a6d2eb7c2fe4316941e.html

大体介绍一下:

增广路的定义(也称增广轨或交错轨):
  若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。
  由增广路的定义可以推出下述三个结论:
  1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M。
  2-P经过取反操作可以得到一个更大的匹配M’。
  3-M为G的最大匹配当且仅当不存在相对于M的增广路径。
  用增广路求最大匹配(称作匈牙利算法,匈牙利数学家Edmonds于1965年提出)
  算法轮廓:
  (1)置M为空
  (2)找出一条增广路径P,通过取反操作获得更大的匹配M’代替M
  (3)重复(2)操作直到找不出增广路径为止
  时间复杂度 邻接矩阵:最坏为O(n^3) 邻接表:O(nm)
  空间复杂度 O(n^2) O(m+n)

这里用网络流求最大匹配,参考题目poj3401 asteroids ,二者本质上是相同的。

这可以通过一点修改,在最大流网络中,加一条S与T之间的路,然后观察最大流每次发现的增广路径实际上通过,这条路全部连起来了,而再观察比较匈牙利算法中的增广路,应该得出实际上它们本质是一个,最大流中的增广实际上也是匈牙利中的增广。

网络流模型,首先需要定义流网络,实际上是由一些节点,及节点间的流量限制组成的一个图。在一个流网络中,节点u,v间的流量限制我们用C(u,v)表示,所有的C(u,v)>=0。对于一个网络,网络中的节点可能不存在边,这样,这样的C(u,v)=0。另外网络中具有两个特殊的点,源点和出点。

模型的目标,是求可以流过该网络的最大流量。


最基本的方法是Ford-Fulkerson,该方法主要借助了三个概念,其中剩余网络,和增广路主要用于计算最大流的过程中。而最小cut,则主要为了证明该方法的正确性。

基本框架是:

Ford-Fulkerson(G,s,t)

init flow f to 0

while there exist a 增广路 p

   沿着增广路,对流进行增加

return f

 利用最大流求最大匹配:

只需要增加一个s和T即可,同时增加S到各点的C(s,i) = 1,和各点到T的C(i,T) = 1.

基本步骤和实现方式如下:

1.

构图,对于图(注意是有向图)的表示可以使用vector <vector<Edge>> G,保存,其中G[i]保存了i的所有以i为起点的边,且该边上C值>0,对于边(u,v)来说,只要C(u,v)或者C(v,u)任意一个大于0,我们就要把u-v,v-u作为边保存到G中,否则不保存.保存的目的,是为了方便后面进行BFS,这样不需要遍历所有顶点,只要看邻接表即可。

而该边上关于该边C的信息可以保存在一个二维数组,也可以保存在Edge结构中。注意:对于某些

2.

初始化,Cf(u,v) = C(u,v),当具有一条有向边(u,v)时C(u,v) = 1,否则C(u,v) = 0,所有的f(u,v)=0.(注意这里的C,f均是一个二维数组,保存了所以u,v对的信息,并非单独针对具有边的那些顶点对)。

3.

寻找增广路,主要是利用Cf(u,v)信息,寻找一条从S到T的路径,在这条路上,所有的Cf(u,v)均大于0.

如果增广路存在,进行4.

否则结束。

4.

沿着增广路,更新流f,和网络容量C,这里要根据你的剩余网络的表示方式,如果你只用一个C数组保存,就要保证当前C减去的是该增广路上C(u,v)的最小值min_c,如果我们用两个数组,分别保存了原始的C和剩余网络的C。则只需要用原始网络的减去当前流f。公式如下

对于增广路上的所有边(u,v),进行如下,更新流f,求剩余网络C:假设分别采用两个数组保存原始的C和剩余网络的C

f(u,v) = f(u,v)+C(u,v)

f(v,u) = 0 - f(u,v)

Cf(u,v) = C(u,v) - f(u,v) 

Cf(v,u) = C(v,u)-f(v,u)

回到3.

注:

第一次写,犯了不少错误。。。

1.

注意所有的C(u,v)>=0 ,但是f(u,v)有的<0 ,这样在求剩余网络的时候,一开始只是简单的把,增广路径上的路径的C(u,v)设成了。实际上漏掉了那些f(u,v)<0的,对于这些,它们的c(u,v)更新之后实际上是大于0的。

如图1,如果沿着红色线路走,应当得到图3的剩余网络,而不是图2的。

最大流和二分匹配 - 星星 - 银河里的星星图1

最大流和二分匹配 - 星星 - 银河里的星星图2最大流和二分匹配 - 星星 - 银河里的星星图3

2.  实际上,虽然bfs之前,将s的父亲设成s,在不断的更新过程中s的父亲是变化的,这样下面利用temp != nodes[temp].parent就无法结束了,导致内存溢出而结束。应该改为temp != s。
            vector <int > path;
            int temp = t;
            while(temp != nodes[temp].parent){
                path.push_back(temp);
                temp =  nodes[temp].parent;//lost it.     
            }   
            path.push_back(temp); 

3.注意bfs过程中,由于C的更新,可能具有环,导致死循环,这样要求bfs过程中需要设一个bool数组,标记已经访问的节点,避免重复访问。

4.对于min_c最好实际计算,而不是想当然的认为是1.

5.在求剩余网络的时候,我实际采用的是一个数组不断保存Cf,但是更新的时候,减的是截至到目前已经积累的流f,这样当然是不正确的,应该用  
                f[u][v] += min_c;
                f[v][u] = 0 - f[u][v];
                c[u][v] = c[u][v] - min_c;
                c[v][u] = c[v][u] + min_c;

6.还有一些小错误,就是比如忘了更新temp
                temp =  nodes[temp].parent;//lost it.

u,v的值一开始取颠倒了
                int u = path[i];
                int v = path[i-1];// u and v exchanged.

 

当然最严重的错误,还是没有搞清楚求剩余网络的过程,忽略了那些f(v,u)小于0的部分

  评论这张
 
阅读(1077)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018