匹配_ACM培训_03.ppt

1、匹配,1.二分图匹配 2.最佳匹配,1.二分图匹配,什么是二分匹配问题？,1.设G是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。 2. 给定一个二分图G，在G的一个子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 3.选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)。,存在奇环的就不是二分图,在ACM竞赛中我们通常遇到的题目是要求我们求一个二分图中的最大匹配数量。对此我们要解决两个问题：,1.建模构图 2.求解二分匹配问题,匈牙利算法,二分图的最大

2、匹配有2种实现，网络流和匈牙利算法。 匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若边集合P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。 由增广路径的定义可以推出下述三个结论： 1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。 2. P经过“取反操作”（即非M中的边变为M中的边，原来M中的边去掉） 可以得到一个更大的匹配M。 3. M为G的最大匹配当且仅当不存在相对于M的增广路径。,图1是我给出的二分图中的一个匹配：2，6和3，7。 图2就是在这个

3、匹配的基础上找到的一条增广路径：1-6-2-7-3-8。这时的匹配数为3个：1，6、2，7和3，8。 图3是在图2的基础上继续找增广路径： 5-1-6-2-7-3 -8-4。 则新的匹配数就比原匹配数增加了1个，为1，5、2，6、3，7、4，8。,匈牙利算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。 算法的流程可以表示如下： (1)置初始匹配M为空 (2)找出一条增广路径P，通过“取反操作”获得更大的匹配M代替M (3)重复(2)操作直到找不出增广路径为止,对于增广路还可以用一个递归的方法来描述。这个描述不一定最准确，但是它揭示了寻找增广路径的一般方法：“从点A出发的增广路

4、”一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匹配中没有与任何点配对，则它就是这条增广路径的终点；反之，如果点B已与点C配对，那么这条增广路径就是从A到B，再从B到C，再加上“从点C出发的增广路径”。并且，这条从C出发的增广路径中不能与前半部分的增广路径有重复的点。,bool map105105,visit105; int match105; int gn,gm; bool dfs(int t) for(int i=1;i=gm;i+) if(!visiti ,int Maxmatch() int num=0,i; memset(match,-1,sizeof(match);

5、for(i=1;i=gn;i+) memset(visit,false,sizeof(visit); if(dfs(i) num+; return num; 用邻接矩阵存储图： 时间复杂度:O(n3) 空间复杂度:O(n2),一般求最大匹配的题目都会出现一些变种：,变种1：二分图的最小顶点覆盖,在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是 二分图的“最小顶点覆盖”。,变种2：DAG图的最小路径覆盖,用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。,结论： 二分图的最小顶点覆盖数 = 二分图的最大匹配数,结论： DAG图的最小路径

6、覆盖数 = 节点数（n）- 最大匹配数（m）,变种3:二分图的最大独立集,在个点的图G中选出m个点，使这m个点两两之间没有边求m最大值 如果图满足二分图条件，则可以用二分图匹配来做,结论： 最大独立集点数 = 节点数（N） - 最大匹配数,一些例题,Poj 1034 The dog task,主人和小狗散步，主人的速度是恒定的，且会历经n个点。 主人历经的点数n(2= n =100) 小狗想去的点数m(0= m =100) 小狗的运动的最大速度是主人散步速度的的两倍。 小狗最多能去几个想去的点。,0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 构图的思想：将行看成点，将数字看成

7、边。,最小点覆盖,Hrbeu oj 1302 Kindergarten,最大独立集,Sample Input 2 3 31 11 22 3 2 3 51 11 22 12 22 3,Sample Output Case 1: 3Case 2: 4,2008 Asia Hefei Regional Contest Online,将陌生人建立关系，而建图后没有关系的实际上就是相互熟悉的人，那么求出的最大独立集，就是建图后没有关系的人，这些人都是相互熟悉的。,2.最佳匹配（最大权匹配）,2.KM算法： 该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点X

8、i的顶标为A i ，顶点Yj的顶标为B j ，顶点Xi与Yj之间的边权为wi,j。在算法执行过程中的任一时刻，对于任一条边(i,j)，A i +Bj=wi,j始终成立。 KM算法的正确性基于以下定理： 若由二分图中所有满足A i +Bj=wi,j的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。,1.什么是最佳匹配问题？,首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是 Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和

9、等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。,初始时为了使A i +Bj=wi,j恒成立，令A i 为所有与顶点Xi关联的边的最大权，Bj=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d。 KuhnMunkras算法流程： (

10、1)初始化可行顶标的值； (2)用匈牙利算法寻找完备匹配； (3)若未找到完备匹配则修改可行顶标的值； (4)重复(2)(3)直到找到相等子图的完备匹配为止；,bool find(int x) visxx = true; for(int i = 0; i n; i+) if(visyi) continue; int t = lxx + lyi - mapxi; if(t = 0) visyi = true; if(matchi = -1 | find(matchi) matchi = x; return true; else if(t slack) slack = t; return fals

11、e; ,int KM() memset(match,-1,sizeof(match); memset(lx,0,sizeof(lx); memset(ly,0,sizeof(ly); for(int i = 0; i lxi) lxi = mapij; for(int i = 0; i n; i+) while(true) memset(visx,false,sizeof(visx); memset(visy,false,sizeof(visy); slack = INF; /INF 是一个假设的无穷大值 if(find(i) break; for(int i = 0; i n; i+) if(visxi) lxi -= slack; if(visyi) lyi += slack; int res = 0; for(int i = 0; i n; i+) res += (lxi + lyi); return res; ,Sample Input 2 10 3 3 A A B A B B C C C C F F E F E E D D D D X X X Y Y Y Y Z Z Z S T R S T R S T R S 3 2 2 A B A C D C F F E,Hdu oj 3718 Similarity,Sam