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

匈牙利算法 有没有更快的算法？ 匈牙利算法是迭代的，也就是说你可以从任何一个初始匹配开始使用匈牙利算法，最后一定能得到一个最大匹配（增广路定理的推论）。 如果先贪心一个初始匹配再使用匈牙利算法，那么程序可能会快很多。 有没有时间复杂度更低的算法？ HOPCROFT-KARP算法 与网络流的优化方法类似，可以考虑每次寻找若干条结点不相交的最短增广路，每次沿多条增广路同时增广，这就是Hopcroft-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)。这是目前已知的对于稀疏图最有效的二分图匹配算法。 Bfs: X1 X2 X3 X4 X5 y1 y2 y3 y4 y5 x1 x2 x3 X4 x5 y1 y2 y3 y4 y5 0 0 0 0 0 1 1 1 1 1 X1 X2 X3 X4 X5 y1 y2 y3 y4 y5 X1 X2 X3 X4 y1 y2 y3 Y4 X1 X2 X3 X4 y1 y2 y3 Y4 x1 x2 x3 X4 y1 y2 y3 y4 0 0 0 0 1 1 1 1 X4 y3 x3 y4 0 1 2 3 X1 X2 X3 X4 y1 y2 y3 Y4 X1 X2 X3 X4 y1 y2 y3 Y4 相关例题 例2. STUDENTS MORNING 题目来源： SGU242 有N个学生要去参观M个学校，要求每个学生至多只能参观一个学校（也可以一个学校都不参观）。分别给出每个学生愿意参观哪些学校，求一个满足每个学校至少有两个学生参观的方案，或输出符合条件的方案不存在。限制：M≤N≤200。 例2. STUDENTS MORNING 容易想到建立如下的网络流模型： 将N个学生作为顶点X1, X2, ……, XN，M个学校作为顶点Y1, Y2, ……, YM。如果学生i愿意参观学校j，那么连边(Xi, Yj)，容量下界为0，上界为1。从源点S向每一个Xi连边，容量下界为0，上界为1。从每一个Yj向汇点T连边，容量下界为2，上界为无穷大。问题转化为求这个网络的一个可行流。 容量有上下界的可行流是不容易计算的，考虑如何简化这个模型。 例2. STUDENTS MORNING 题目规定每个学校至少有两个学生参观，而多于两个人参观同一个学校是没有任何意义的，所以不妨限制每个学校最多有两个学生参观。 建立如下的网络流模型：基本与上一个模型相同，只是每一个Yj向汇点T连的边容量下界改为0，上界改为2。求出S到T的最大流F，如果F=2M则找到了一个可行的方案。 这个方法要比上一个简单得多，但似乎还是有点麻烦。 例2. STUDENTS MORNING 考虑到建立的模型是个二分图，但不同的是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。 由此可知，要使路径数最少，就要使得覆盖中的边数最多。因为每个顶点只能出现在一条路径上，所以最多是进来一次，出去一次，这就让我们联想到了图的匹配。 有向无环图的最小路径覆盖是一个经典问题，建模用到了