《二分匹配匈牙利算法》由会员分享，可在线阅读，更多相关《二分匹配匈牙利算法（23页珍藏版）》请在金锄头文库上搜索。
1、ACM/ICPC暑期集训讲座 二分图匹配 cnhawk 2007.7.25 经典问题工作分配 l一个公司有n个工作岗位空缺，每个岗位空 缺需要有一定资格的人来填补。现在有m个 人申请这n个工作。由于每个人工作能力不 同，所以不同的人能胜任不同的工作。 l现在已知每个人所能胜任的若干工作，求 这m个人最多可以填补几个工作岗位。 l每个人只能做一份工作，每个工作岗位也 只需要一个人 二分图的一般表述 l一个图的点，可以分割成两个集合X和Y l在集合内部没有边 l任何一条边的两个端点都分属不同的集合 匹配 l在工作分配的问题中，我们给出一个可行 的分配方案，就是一个匹配。如果这个匹 配是最优的（可以
2、填补的工作岗位最多） ，就是最大匹配。 匹配 l匹配的一般定义：匹配是二分图所有边的 一个子集，在这个子集中任意两条边都没 有公共点。 l最大匹配：边数最多的一个匹配 l*覆盖的概念：与匹配相关的顶点集 二分图最大匹配问题 l现在，工作分配问题变成了求一个二分图 中最大匹配的问题。 l二分匹配的经典算法： 匈牙利算法（Ford-Fulkerson算法的变形） 基本概念 l左边右边 l交错链（增广路） 对于一个已有的匹配而言 从未被覆盖的点出发，寻 找一个交错链。 交错链长度为奇数，它上 面的边依次为：未选，已 选，未选，已选未选 交错链 交错链 l几个重要的性质： 1.对于一个已有的匹配（可以
3、为空匹配 ）可以通过更改交错链上的边来获取更大 的匹配 2.如果我们找到了一个匹配，并且再也 找不到交错链了，那么这个匹配是最大匹 配 匈牙利算法 l匈牙利算法的思路就是：不停地在一个二 分图中寻找交错链，直到找不到为止。 l寻找交错链可以用BFS或DFS，其中BFS效 率很高，但实现较复杂。 寻找交错链的算法 l1，从左某一个未被匹配的点开始寻找，把 所有与它相连的点加进队列 l2，如果在右边找到一个未被匹配的点，则 算法结束 l3，如果在右边找到一个已经被匹配了的点 ，则看看它是与左边的那个点相匹配的， 从相匹配的那个点出发在右边找其它的点 ，把它们加入队列 寻找交错链 l对每一个左边的没
4、 有被匹配的点进行 BFS，如果在右边 直接找到一个点没 有被匹配，那么我 们就可以增加一条 匹配的边 寻找交错链 l对每一个左边的没 有被匹配的点进行 BFS，如果在右边 直接找到一个点没 有被匹配，那么我 们就可以增加一条 匹配的边 寻找交错链 l对每一个左边的没 有被匹配的点进行 BFS，如果在右边 直接找到一个点没 有被匹配，那么我 们就可以增加一条 匹配的边 2 4 寻找交错链 l寻找交错链：如果 在右边找到一个已 经被匹配了的点， 则看看它是与左边 的哪个点相匹配的 ，从相匹配的那个 点出发在右边找其 它的点，把它们加 入队列 寻找交错链 寻找交错链的算法 l1，从左某一个未被匹配
5、的点开始寻找，把 所有与它相连的点加进队列 l2，如果在右边找到一个未被匹配的点，则 算法结束 l3，如果在右边找到一个已经被匹配了的点 ，则看看它是与左边的哪个点相匹配的， 从相匹配的那个点出发在右边找点，把它 们加入队列 代码（模板） lBipartite.cpp l二分图匹配（邻接矩阵表示） l邻接表的图需要修改一下 复杂度分析 l对于一个有V个点，E条边的二分图 l每一次BFS的复杂度为O(E) l可以证明，对于每一个左边的点最多进行 一次BFS就可以找到一个最大匹配 l所以总的复杂度是O(VE) 经典问题棋盘覆盖 l在一个m行n列的棋盘上，有些点被禁止， 问能否用1x2的多米诺骨牌覆盖其他位置？ l如果不能全部覆盖，则最多可以覆盖多少 个小格？ 经典问题棋盘覆盖 lFZU-1467 与这个问题几乎一样 l解决思路： 先给棋盘染色！ 经典问题棋盘覆盖 l将棋盘染成黑白二色 ，则：任意一个多米 诺骨牌必定会覆盖一 个白色的格子和一个 黑色的格子！ l问题变成了黑点与白 点之间的二分匹配， 相邻的点之间有一条 边。 作业 lTOJ-1050 lFZU-1467(数据范围较大，必须用邻接表实 现) l二分图匹配是一个比较难的内容，如果不 能深入了解算法，可以先搞清楚它可以解 决哪些问题，遇到此类问题只要套上模板 就可以AC
