二分匹配匈牙利算法

1、二分匹配匈牙利算法第1页，共22页。经典问题工作分配一个公司有n个工作岗位空缺，每个岗位空缺需要有一定资格的人来填补。现在有m个人申请这n个工作。由于每个人工作能力不同，所以不同的人能胜任不同的工作。现在已知每个人所能胜任的若干工作，求这m个人最多可以填补几个工作岗位。每个人只能做一份工作，每个工作岗位也只需要一个人第2页，共22页。二分图的一般表述一个图的点，可以分割成两个集合X和Y在集合内部没有边任何一条边的两个端点都分属不同的集合第3页，共22页。匹配在工作分配的问题中，我们给出一个可行的分配方案，就是一个匹配。如果这个匹配是最优的（可以填补的工作岗位最多），就是最大匹配。第4页，共22

2、页。匹配匹配的一般定义：匹配是二分图所有边的一个子集，在这个子集中任意两条边都没有公共点。最大匹配：边数最多的一个匹配*覆盖的概念：与匹配相关的顶点集第5页，共22页。二分图最大匹配问题现在，工作分配问题变成了求一个二分图中最大匹配的问题。二分匹配的经典算法：匈牙利算法（Ford-Fulkerson算法的变形）第6页，共22页。基本概念左边右边交错链（增广路）对于一个已有的匹配而言从未被覆盖的点出发，寻找一个交错链。交错链长度为奇数，它上面的边依次为：未选，已选，未选，已选未选第7页，共22页。交错链第8页，共22页。交错链几个重要的性质：1.对于一个已有的匹配（可以为空匹配）可以通过更改交错

3、链上的边来获取更大的匹配2.如果我们找到了一个匹配，并且再也找不到交错链了，那么这个匹配是最大匹配第9页，共22页。匈牙利算法匈牙利算法的思路就是：不停地在一个二分图中寻找交错链，直到找不到为止。寻找交错链可以用BFS或DFS，其中BFS效率很高，但实现较复杂。第10页，共22页。寻找交错链的算法1，从左某一个未被匹配的点开始寻找，把所有与它相连的点加进队列2，如果在右边找到一个未被匹配的点，则算法结束3，如果在右边找到一个已经被匹配了的点，则看看它是与左边的那个点相匹配的，从相匹配的那个点出发在右边找其它的点，把它们加入队列第11页，共22页。寻找交错链对每一个左边的没有被匹配的点进行BFS

4、，如果在右边直接找到一个点没有被匹配，那么我们就可以增加一条匹配的边第12页，共22页。寻找交错链对每一个左边的没有被匹配的点进行BFS，如果在右边直接找到一个点没有被匹配，那么我们就可以增加一条匹配的边第13页，共22页。寻找交错链对每一个左边的没有被匹配的点进行BFS，如果在右边直接找到一个点没有被匹配，那么我们就可以增加一条匹配的边24第14页，共22页。寻找交错链寻找交错链：如果在右边找到一个已经被匹配了的点，则看看它是与左边的哪个点相匹配的，从相匹配的那个点出发在右边找其它的点，把它们加入队列第15页，共22页。寻找交错链第16页，共22页。寻找交错链的算法1，从左某一个未被匹配的点

5、开始寻找，把所有与它相连的点加进队列2，如果在右边找到一个未被匹配的点，则算法结束3，如果在右边找到一个已经被匹配了的点，则看看它是与左边的哪个点相匹配的，从相匹配的那个点出发在右边找点，把它们加入队列第17页，共22页。代码（模板）Bipartite.cpp二分图匹配（邻接矩阵表示）邻接表的图需要修改一下第18页，共22页。复杂度分析对于一个有V个点，E条边的二分图每一次BFS的复杂度为O(E)可以证明，对于每一个左边的点最多进行一次BFS就可以找到一个最大匹配所以总的复杂度是O(VE)第19页，共22页。经典问题棋盘覆盖在一个m行n列的棋盘上，有些点被禁止，问能否用1x2的多米诺骨牌覆盖其他位置？如果不能全部覆盖，则最多可以覆盖多少个小格？第20页，共22页。经典问题棋盘覆盖FZU-1467 与这个问题几乎一样/problem.php?pid=1467解决思路：先给棋盘染色！第21页，共22页。经典问题棋