二分图最大匹配及其应用.ppt

二分图最大匹配及其应用
二分图与图的匹配
例1. THE PERFECT STALL
题目来源：USACO, POJ1274
农夫John的牛棚共有M个牛栏，其中一共养了N头奶牛。每头奶牛只愿意在它喜欢的那些牛栏中产奶。一个牛栏只能容纳一头奶牛，一头奶牛也只在一个牛栏中产奶。请你将奶牛分配到牛栏中，使得愿意产奶的奶牛数T最大。限制：N≤200，M≤200。
例1. THE PERFECT STALL
样例：N=5, M=5
方案：1-5, 2-3, 3-1, 5-2
解释：5号奶牛只能去2号，那么1号奶牛只能去5号，3号奶牛只能去1号，于是4号奶牛无论如何都不能被分配到喜欢的牛栏。
奶牛编号
喜欢的牛栏
1
2, 5
2
2, 3, 4
3
1, 5
4
1, 2, 5
5
2
例1. THE PERFECT STALL
如果题目的规模比较小，那么有什么方法？
暴力搜索：O(N!)，当N≥12时已经难以在时限内出解。
在暴力搜索的基础上优化？
状态压缩+记忆化搜索（动态规划）
例1. THE PERFECT STALL
考虑用图论模型来表示题给的条件。
将每一头奶牛、每一个牛栏都作为图的顶点：i号奶牛对应顶点Xi，j号牛栏对应顶点Yj。如果i号奶牛喜欢j号牛栏，那么连边(Xi, Yj)。
例1. THE PERFECT STALL
注意到如果对于1号奶牛选择1号牛栏，2号奶牛选择2号牛栏的情况，答案为t，那么对于1号奶牛选择2号牛栏，2号奶牛选择1号牛栏的情况（即交换两头奶牛选择的牛栏），答案仍为t。从中得到启发，其实很多状态是冗余的。
只需记录有哪些奶牛和牛栏没有被用过，答案就确定了，而那些用过的奶牛和牛栏不需要考虑。
例1. THE PERFECT STALL
用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. THE PERFECT STALL
由于转移的时间复杂度为O(M)，所以总的时间复杂度为O(M2M) 。空间复杂度似乎也是O(M2M)。
注意到每当i减少1时，S中含的元素也会少1个，所以通过S就可以唯一确定i，因此状态中只需要记录S，从而空间复杂度降为O(2M)。
这个算法可以解决N≤20的数据。
如果规模更大，还有办法解决吗？
例1. THE PERFECT STALL
不难发现这个图的特点：可以将图的顶点划分为两个集合X, Y，使得图的任何一条边的一个端点在X中，另一个端点在Y中。满足这个条件的图称为二分图（二部图）。
可以证明，一个图是二分图等价于图中不含长度为奇数的环。
对于一个二分图G，如果X中的每个顶点都与Y中的每个顶点有边相连，则称G为完全二分图。