二分图最大匹配及其应用

北京大学元培学院吕伟聪二分图最大匹配及其应用二分图与图的匹配二分图的概念匹配的概念例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的最大匹配。要求一般图的最大匹配是比较困难的，但是求二分图的匹配就容易得多。本题就是求二分图最大匹配的问题。匹配的概念求二分图最大匹配的算法网络流匈牙利算法Hopcroft-Karp转化为求最大流的问题可以将求二分图最大匹配的问题转化为最大流的问题。增加两个顶点S、T。对于X中的每个顶点Xi，连边(S,Xi)，容量为1。对于Y中的每个顶点Yj，连边(Yj,T)，容量为1。对于原图中的边(Xi,Yj)，将容量设为1。显而易见，S到T的最大流就是原图的最大匹配。建立网络流模型匈牙利算法然而，用网络流算法求最大匹配，显得过于麻烦。利用二分图的特殊性质，将求最大流的Edmonds-Karp算法简化，就得到了匈牙利算法。匈牙利算法的实质匈牙利算法设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。初始匹配常常选取成空的，即一开始所有的顶点都是未盖点。实现过程匈牙利算法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

end

if

end

if

end

for

returnfalseend

function伪代码——增广匈牙利算法s←0l[1..m]←0fori←1tonc[1..m]←false

iffind(i)s←s+1

end

ifend

for伪代码——主程序匈牙利算法设二分图中有n个顶点，m条边，则每次寻找增广路的时间复杂度为O(m)，而一共要寻找O(n)次，所以总的时间复杂度为O(nm)。如果是稠密图（比如完全二分图），那么时间复杂度为O(n3)。用邻接表存储，空间复杂度为O(m)。如果是稠密图，那么往往用邻接矩阵存储，空间复杂度为O(n2)。复杂度分析匈牙利算法有没有更快的算法？匈牙利算法是迭代的，也就是说你可以从任何一个初始匹配开始使用匈牙利算法，最后一定能得到一个最大匹配（增广路定理的推论）。如果先贪心一个初始匹配再使用匈牙利算法，那么程序可能会快很多。有没有时间复杂度更低的算法？优化Hopcroft-Karp算法与网络流的优化方法类似，可以考虑每次寻找若干条结点不相交的最短增广路，每次沿多条增广路同时增广，这就是Hopcroft-Karp算法。Hopcroft-Karp算法与匈牙利算法的关系类似于Dinic算法与Edmonds-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)。这是目前已知的对于稀疏图最有效的二分图匹配算法。沿着最短路增广相关例题拆点法参数搜索……例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之后直接用匈牙利算法计算整个图的最大匹配，那么时间复杂度高达O(NM2)，是难以承受的。枚举答案例4.最小最大匹配不妨这样考虑：每当k增加时，都只是在原图上加了一条边Ek=(Xi,Yj)，显然匹配数要么多了1，要么不变。现在考虑能否利用前k-1条边已经求出的一个最大匹配来快速得到新图的最大匹配。如果Xi是未盖点，那么很简单，直接从顶点Xi出发寻找增广轨即可（由Xi是未盖点可知Xi不可能是某条增广轨的中间顶点，所以若存在增广轨，那么Xi一定是它的端点）。在之前的答案上进行修正例4.最小最大匹配如果Xi不是未盖点，Yj是未盖点，那么类似地从Yj出发寻找增广轨。如果Xi和Yj都不是未盖点，那么图中不存在包含边Ek的增广轨，所以在这个新图中一定找不出增广轨。分情况讨论例4.最小最大匹配于是我们得到了另一个算法：按照权值从小到大枚举每一条边，将它加入二分图后求出最大匹配，如果得到了完备匹配那么最后加进去的边的权值就是答案。这个算法的时间复杂度为O(NM)，是很优秀的算法。算法实现复杂度分析例4.最小最大匹配事实上，本题还有另一个比较简洁的思路。直接求答案看起来似乎比较困难，现在我们先考虑一个简单一些的问题：给出x，判断是否有一个完备匹配，满足这个匹配中权值最大的边的权值不超过x。参数搜索转化为判定性问题例4.最小最大匹配显然，如果存在满足条件的匹配，那么这个匹配中不含权值大于x的边。因此，将图中权值大于x的边全部删去，那么只要新图存在一个完备匹配，那么这个匹配中权值最大的边的权值一定不超过x。判断是否存在完备匹配可以使用匈牙利算法来完成。判定性问题例4.最小最大匹配解决了这个简单一些的问题后，原问题也就解决了。设输入中最小的边权和最大的边权分别为L和R，那么答案一定在[L,R]中。之后就可以用二分的方法求出答案：取x=(L+R)/2，用上面的方法判断是否存在一个最大权值不超过x的完备匹配。如果存在，那么最优解一定在[L,x]中，否则最优解在(x,R]中。对于这个长度缩小了一半的区间不断重复上面的算法，就可以得到最优解。二分答案例4.最小最大匹配一共需要进行O(logM)次匈牙利算法，而匈牙利算法的时间复杂度为O(NM)。于是这个算法的总时间复杂度为O(NMlogM)。事实上，遇到要求“最大值最小”或者“最小值最大”的问题时，首先就应该思考能否用二分答案的方法来解决。试着将最优性问题转化为判定性问题，有时可以将问题简化。复杂度分析例5.BelovedSons题目来源：SGU210国王有N个儿子，每个儿子都喜欢一些女孩。现在每个儿子要娶一个女孩（一个女孩只能嫁给国王的一个儿子）。每个儿子有一个权值Ai，如果他娶的是自己喜欢的女孩，则满意度为Ai，否则为0。求一个分配方案，使得所有儿子的满意度之和最大。限制：N≤400。题目描述例5.BelovedSons不难建立如下的二分图模型：将每个男孩作为X中的顶点，每个女孩作为Y中的顶点，建立一个二分图。如果男孩i喜欢女孩j，则连边(Xi,Yj)，权值为Ai。于是问题变为求这个二分图的权值和最大的匹配，即最大权匹配（最佳匹配）。求二分图的最佳匹配可以用KM算法解决，时间复杂度为O(N4)，经过优化后可以达到O(N3)。最大权匹配例5.BelovedSons有没有更简单的方法呢？本题的特殊性在于从顶点Xi连出的所有边的权值都是相等的。也就是说，总的满意度只和每个男孩有没有娶喜欢的女孩有关，而和具体娶的是哪一个女孩无关。题目的特殊性例5.BelovedSons于是想到了贪心法：将所有的男孩按照Ai值从大到小排序，则应该优先满足前面的男孩的要求，而如果后面某个男孩为了娶喜欢的女孩而与前面的男孩不可避免地要冲突，那么为了总权值最大，只能牺牲后面的男孩。贪心法例5.BelovedSons注意到匈牙利算法有一个特点：如果一个顶点已经被匹配上了，那么随着算法的进行，它永远都是被匹配上的。所以在将男孩排好序之后，依次作为起点使用匈牙利算法找增广路，如果找到了就匹配上，否则就让这个男孩娶他不喜欢的女孩。这个算法能保证总是优先满足前面的男孩的要求，所以是正确的。总时间复杂度为匈牙利算法的时间复杂度，即O(N3)，但要比前面的算法简单一些。匈牙利算法的特点例6.PizzaOrder题目来源：POJ2009有T种馅料，每个匹萨都会正好包含其中的K种。现在有C头奶牛。每头牛都有一个喜欢的馅料的集合，如果一个匹萨含有的所有馅料都属于这个集合，那么这头牛就可以吃这种匹萨。问最多能让多少头奶牛吃到匹萨，且没有两头牛吃的匹萨所含馅料完全相同。限制：K≤T≤30，C≤1000。题目描述例6.PizzaOrder为了使得吃到匹萨的奶牛最多，显然每头奶牛至多只应该吃一种匹萨。而每种匹萨只能被一头奶牛吃，从而联想到二分图匹配：将所有奶牛看成X部的顶点，所有不同的匹萨看成Y