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