ACM讲课之二分图匹配(匈牙利算法)-PPT

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ACM讲课之二分图匹配(匈牙利算法),什么是二分图？,在离散数学中，我们都学过偶图，而偶图就是二分图。,二分图,：给你一个图，它的顶点可以分为两个集合，集合,V1,和,V2,，所有关联边的一个顶点在,V1,中，另一个顶点则在,V2,中。,v1,v2,v3,v4,v5,v1,v2,v3,v4,二分图,非二分图,2,什么是二分图匹配？,二分图匹配,：给定一个二分图,G,，在,G,的一个子图,M,中，,M,的边集中的任意两条边都不依附于同一个顶点，则称,M,是一个匹配。,v1,v2,v3,v4,v5,v1,v2,v3,v4,v5,匹配,1,匹配,2,3,二分图的最大匹配,最大匹配,：图中包含边数最多的匹配称为图的最大匹配。,今天我要讲的是无权二分图的最大匹配问题，采用匈牙利算法。,4,匈牙利算法必备知识,：,1.,盖点,：有被,M,中的边关联到的节点，,未盖点,则相反。,2.,增广路径,：若二分图中有一条路径,p,，其起始点和结束点都是未盖点，其间属于,M,的边和不属于,M,的边交替出现，则称路径,p,是一条关于,M,的增广路径,。,匈牙利算法,：,计算二分图最大匹配就是应用增广路径的概念，每次寻找一条关于,M,的增广路径,p,，通过,M,和增广路径进行异或，使得,M,中的匹配数增加,1,。以此类推，直至二分图中不存在关于,M,的增广路径为止。此时得到匹配,M,就是图,G,的一个最大匹配。,注：,M,为一个边集，,M,就是二分图的匹配,5,结合增广路径的定义和下图所示，我们可以理解以下结论：,1.,增广路径的长度必定为奇数，第一条边和最后一条边都不属于,M,。,2.,将,M,和增广路径进行异或操作（去同存异）可以得到一个更大的匹配,M,。,3.M,比,M,的匹配数多,1,。,4.M,为,G,的最大匹配当且仅当不存在,M,的增广路径。,核心,：,判断当前结点为起点的增广路径是否存在,。,6,poj1274,题目大意,：有,N,头奶牛，,M,个产奶的棚子，每头奶牛都有自己想去产奶的几个棚子，问可以产生的最大匹配数。,数据：,Sample Input,5 5 N M,2 2 5,第一头：,t m2 m5,3 2 3 4,第二头：,t m2 m3 m4,2 1 5,第三头：,.,3 1 2 5,第四头：,.,1 2,第五头：,.,Sample Output,4,7,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,8,解题思路,：将奶牛看成,N,集合，棚子看成,M,集合,1,对于,N,集合中一个未匹配的节点,i,寻找它的每条关联边,如果它的边上的另一个节点,j,还没匹配则表明找到了一个匹配,直接转步骤,4;,2,假如节点,i,它边上的另一个节点,j,已经匹配,那么就转向跟,j,匹配的节点，也就是它的前驱,假设是,prej,然后再对,prej,重复,1,2,的步骤,即,寻找增广路径,.,3,假如我们在,1,2,步过程中找到一条增广路,那么修改各自对应的匹配点,转步骤,4,若无增广路,则退出,.,4,匹配数,+1;,9,2,3,4,5,5,4,3,2,1,1,2,3,4,5,5,4,3,2,1,1,10,2,3,4,5,5,4,3,2,1,1,i=1,时：,Pre2=1;,11,2,3,4,5,5,4,3,2,1,1,1,2,3,i=2,时：,Pre5=1;,Pre2=2;,12,2,3,4,5,5,4,3,2,1,1,1,i=3,时：,Pre1=3;,13,2,3,4,5,5,4,3,2,1,1,i=4,时：,Pre3=2;,Pre2=1;,Pre5=3;,Pre1=4;,14,