二分图最大匹配及其应用

二分图最大匹配及其应用二分图与图的匹配例1.THEPERFECTSTALL题目来源：USACO,POJ1274农夫John的牛棚共有M个牛栏，其中一共养了N头奶牛。每头奶牛只愿意在它喜欢的那些牛栏中产奶。一个牛栏只能容纳一头奶牛，一头奶牛也只在一个牛栏中产奶。请你将奶牛分配到牛栏中，使得愿意产奶的奶牛数T最大。限制：N≤200，M≤200。例1.THEPERFECTSTALL样例：N=5,M=5方案：1-5,2-3,3-1,5-2解释：5号奶牛只能去2号，那么1号奶牛只能去5号，3号奶牛只能去1号，于是4号奶牛无论如何都不能被分配到喜欢的牛栏。奶牛编号喜欢的牛栏12,522,3,431,541,2,552例1.THEPERFECTSTALL如果题目的规模比较小，那么有什么方法？暴力搜索：O(N!)，当N≥12时已经难以在时限内出解。在暴力搜索的基础上优化？状态压缩+记忆化搜索（动态规划）例1.THEPERFECTSTALL考虑用图论模型来表示题给的条件。将每一头奶牛、每一个牛栏都作为图的顶点：i号奶牛对应顶点Xi，j号牛栏对应顶点Yj。如果i号奶牛喜欢j号牛栏，那么连边(Xi,Yj)。例1.THEPERFECTSTALL注意到如果对于1号奶牛选择1号牛栏，2号奶牛选择2号牛栏的情况，答案为t，那么对于1号奶牛选择2号牛栏，2号奶牛选择1号牛栏的情况（即交换两头奶牛选择的牛栏），答案仍为t。从中得到启发，其实很多状态是冗余的。只需记录有哪些奶牛和牛栏没有被用过，答案就确定了，而那些用过的奶牛和牛栏不需要考虑。例1.THEPERFECTSTALL用f[i][S]表示在前i头奶牛已经选择的牛栏集合为S的情况下，其余的奶牛最多能有多少可以选择喜欢的牛栏。S是一个二进制数，其中S的第k位如果是1则表示k号牛栏已经被使用，否则k号牛栏可以被后面的奶牛使用。对于状态f[i][S]，枚举i号奶牛使用的牛栏j（要满足S的第j位是0），则f[i][S]就是所有f[i-1][S-{j}]的最大值加1。例1.THEPERFECTSTALL由于转移的时间复杂度为O(M)，所以总的时间复杂度为O(M2M)。空间复杂度似乎也是O(M2M)。注意到每当i减少1时，S中含的元素也会少1个，所以通过S就可以唯一确定i，因此状态中只需要记录S，从而空间复杂度降为O(2M)。这个算法可以解决N≤20的数据。如果规模更大，还有办法解决吗？例1.THEPERFECTSTALL不难发现这个图的特点：可以将图的顶点划分为两个集合X,Y，使得图的任何一条边的一个端点在X中，另一个端点在Y中。满足这个条件的图称为二分图（二部图）。可以证明，一个图是二分图等价于图中不含长度为奇数的环。对于一个二分图G，如果X中的每个顶点都与Y中的每个顶点有边相连，则称G为完全二分图。例1.THEPERFECTSTALL本题就是要求从图中选出尽可能多的边，满足每个顶点至多是其中一条边的端点。设G=(V,E)是一个图，M是E的一个子集。如果M中的任何两条边都没有共同的端点，则称M为G的一个匹配。G中边数最多的匹配称为G的最大匹配。要求一般图的最大匹配是比较困难的，但是求二分图的匹配就容易得多。本题就是求二分图最大匹配的问题。求二分图最大匹配的算法转化为求最大流的问题可以将求二分图最大匹配的问题转化为最大流的问题。增加两个顶点S、T。对于X中的每个顶点Xi，连边(S,Xi)，容量为1。对于Y中的每个顶点Yj，连边(Yj,T)，容量为1。对于原图中的边(Xi,Yj)，将容量设为1。显而易见，S到T的最大流就是原图的最大匹配。匈牙利算法然而，用网络流算法求最大匹配，显得过于麻烦。利用二分图的特殊性质，将求最大流的算法简化，就得到了匈牙利算法。匈牙利算法设M是图G=(V,E)的一个匹配。若顶点v是M中某条边的端点，则称v是M的饱和点，否则称v为M的非饱和点（未盖点）。如果G的每个顶点都是M的饱和点，则称M是G的一个完备匹配（完美匹配）。匈牙利算法设M是G的一个匹配，P是G的一条链。如果P的边交替地一条是M中的边，一条不是M中的边，则称P为M的交错轨。如果交错轨P连接的是两个非饱和点，则称P是增广路（增广链，增广轨）。不难发现，对于增广路P，将在M中的边删去，而将不在M中的边加上，那么得到的仍然是一个匹配，但匹配数增加了1。这就是匈牙利算法的原理。匈牙利算法形象化地说，就是从二分图中找出一条路径，使得路径的起点和终点都是没有被匹配的点，而且路径经过的边是一条没被匹配，一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的边比已经匹配了的边多一条，于是修改匹配图，把路径里所有匹配过的边去掉，把没有匹配的边变成匹配的，这样一来匹配数就比原来多了1。不断执行上述操作，直到找不到这样的路径为止。匈牙利算法当找不到增广路时，能否保证得到的匹配是最大匹配呢？可以，因为我们有增广路定理：一个匹配是最大匹配当且仅当没有增广路。注意，这个定理适用于任意图。匈牙利算法由增广路定理定理可知，从任何一个匹配开始，不断沿着增广路增广，一定能得到一个最大匹配。于是就得到了匈牙利算法：从一个初始匹配开始，不断找增广路并进行增广，直到找不到增广路为止，那么最后得到的就是最大匹配。寻找增广路可以用BFS或DFS。初始匹配常常选取成空的，即一开始所有的顶点都是未盖点。图例X1X2X3X4X5y1y2y3y4y5X1X2X3X4X5y1y2y3y4y5X1X2X3X4X5y1y2y3y4y5X1X2X3X4X5y1y2y3y4y5X1X2X3X4X5y1y2y3y4y5X1X2X3X4X5y1y2y3y4y5X1X2X3X4X5y1y2y3y4y5X1X2X3X4X5y1y2y3y4y5匈牙利算法functionfind(i):booleanforj←1tomifg[i][j]and(notc[j])c[j]←trueif(l[j]=0)orfind(l[j])l[j]←ireturntrueendifendifendforreturnfalseendfunction匈牙利算法s←0l[1..m]←0fori←1tonc[1..m]←falseiffind(i)s←s+1endifendfor匈牙利算法设二分图中有n个顶点，m条边，则每次寻找增广路的时间复杂度为O(m)，而一共要寻找O(n)次，所以总的时间复杂度为O(nm)。如果是稠密图（比如完全二分图），那么时间复杂度为O(n3)。用邻接表存储，空间复杂度为O(m)。如果是稠密图，那么往往用邻接矩阵存储，空间复杂度为O(n2)。匈牙利算法有没有更快的算法？匈牙利算法是迭代的，也就是说你可以从任何一个初始匹配开始使用匈牙利算法，最后一定能得到一个最大匹配（增广路定理的推论）。如果先贪心一个初始匹配再使用匈牙利算法，那么程序可能会快很多。有没有时间复杂度更低的算法？HOPCROFT-KARP算法与网络流的优化方法类似，可以考虑每次寻找若干条结点不相交的最短增广路，每次沿多条增广路同时增广，这就是Hopcroft-Karp算法。可以证明，如果每次都是沿着尽可能多的最短增广路同时增广，那么总的增广的次数仅为O(n0.5)，相比于匈牙利算法（增广n次）要好很多。HOPCROFT-KARP算法问题的关键在于用O(m)的时间找出尽量多的最短增广路。首先从所有X的未盖点进行BFS（仍然是找增广路），计算每个X的顶点和Y的顶点的距离。如果Y中有未盖点被访问到，就找到了增广路，但找到Y中的第一个未盖点时并不停止，而是等找出所有距离与Y相等的顶点后停止。这样，找到的所有未盖点的距离都相同，而且都是最短增广路。HOPCROFT-KARP算法之后对于Y部的每个未盖点，用DFS寻找增广路（只沿着距离减1的边移动）进行增广（或对于X部的每个未盖点，沿着距离加1的边寻找增广路）。注意在整个DFS的过程中要将访问过的顶点做标记，以保证增广路都是不相交的。增广的次数为O(n0.5)，又因为每次增广的时间复杂度为O(m)，所以总时间复杂度为O(n0.5m)。这是目前已知的对于稀疏图最有效的二分图匹配算法。Bfs:X1X2X3X4X5y1y2y3y4y5x1x2x3X4x5y1y2y3y4y50000011111X1X2X3X4X5y1y2y3y4y5X1X2X3X4y1y2y3Y4X1X2X3X4y1y2y3Y4x1x2x3X4y1y2y3y400001111X4y3x3y40123X1X2X3X4y1y2y3Y4X1X2X3X4y1y2y3Y4相关例题例2.STUDENT'SMORNING题目来源：SGU242有N个学生要去参观M个学校，要求每个学生至多只能参观一个学校（也可以一个学校都不参观）。分别给出每个学生愿意参观哪些学校，求一个满足每个学校至少有两个学生参观的方案，或输出符合条件的方案不存在。限制：M≤N≤200。例2.STUDENT'SMORNING容易想到建立如下的网络流模型：将N个学生作为顶点X1,X2,……,XN，M个学校作为顶点Y1,Y2,……,YM。如果学生i愿意参观学校j，那么连边(Xi,Yj)，容量下界为0，上界为1。从源点S向每一个Xi连边，容量下界为0，上界为1。从每一个Yj向汇点T连边，容量下界为2，上界为无穷大。问题转化为求这个网络的一个可行流。容量有上下界的可行流是不容易计算的，考虑如何简化这个模型。例2.STUDENT'SMORNING题目规定每个学校至少有两个学生参观，而多于两个人参观同一个学校是没有任何意义的，所以不妨限制每个学校最多有两个学生参观。建立如下的网络流模型：基本与上一个模型相同，只是每一个Yj向汇点T连的边容量下界改为0，上界改为2。求出S到T的最大流F，如果F=2M则找到了一个可行的方案。这个方法要比上一个简单得多，但似乎还是有点麻烦。例2.STUDENT'SMORNING考虑到建立的模型是个二分图，但不同的是Y部的顶点最多可以连两条边，于是想到了“拆点”的方法。将N个学生作为顶点X1,X2,……,XN，将每个学校j拆成两个顶点Yj和Yj’。如果学生i愿意参观学校j，那么连边(Xi,Yj)和(Xi,Yj’)。求出这个二分图的最大匹配C，则C就等于上一个模型中的最大流F。例3.最小路径覆盖题目来源：经典问题给出一个含N个顶点的有向无环图G。用尽量少的不相交路径覆盖G的所有顶点，即每个顶点严格属于一条路径。允许路径的长度为0，即只含一个顶点。例3.最小路径覆盖因为含n条边的路径共覆盖了n+1个顶点，所以对于任何一个路径覆盖，有一个显然的关系：路径数+路径覆盖中的边数=N。由此可知，要使路径数最少，就要使得覆盖中的边数最多。因为每个顶点只能出现在一条路径上，所以最多是进来一次，出去一次，这就让我们联想到了图的匹配。有向无环图的最小路径覆盖是一个经典问题，建模用到了前面提到过的“拆点”方法。例3.最小路径覆盖将每一个顶点k拆成两个顶点Xk和Yk，分别表示从顶点k出去和进入顶点k。对于原图中的每条有向边(i,j)，连边(Xi,Yj)，表示可以从顶点i出去之后到进入顶点j。求出这个二分图的最大匹配，就得到了原图的覆盖中最多能有多少条边，即最小路径覆盖中的边数=二分图最大匹配数。因此由最小路径覆盖数=N-最小路径覆盖中的边数就得到了答案。例4.最小最大匹配题目来源：经典问题给出一个带权二分图，其中X部和Y部各有N个顶点。求一个完备匹配，满足匹配边中权值最大的边的权值尽量小。例4.最小最大匹配设这个二分图中有M条边。先将所有的边按照权值从小到大排序，设为E1,E2,……,EM。从小到大依次枚举每一条边Ek，判断仅用边E1,E2,……,Ek能否使得二分图存在一个完备匹配。如果存在，那么答案就是边Ek的权值。如果枚举k之后直接用匈牙利算法计算整个图的