算法合集之《浅析二分图匹配在信息学竞赛中的应用》.pptVIP

浅析二分图匹配在信息学竞赛中的应用 长郡中学 王俊 引言 二分图匹配是一类经典的图论算法，在近年来信息学竞赛中有广泛的应用。 二分图和匹配的基础知识已经在前辈的集训队论文中有过介绍，本文主要通过一道例题研究其应用。 [例题] Roads 请求出修改的最小代价。 给定一个无向图G0=（V0，E0，C），V0为顶点集合,E0为边集合（无重边），C为边权（非负整数）。设n= |V0|，m= |E0|，E0中前n-1条边构成一棵生成树T。请将边权进行如下修改，即对于e∈E，把Ce修改成De（De也为非负整数），使得树T成为图G的一棵最小生成树。修改的代价定义为： 4 6 2 2 3 5 7 4 4 2 4 3 3 4 f=|6-4|+|2-2|+|5-3|+|7-4|+|3-3|+|2-4|+|4-4|=9 初步分析 根据与树T的关系,我们可以把图G0中的边分成树边与非树边两类。 设Pe表示边e的两个端点之间的树的路径中边的集合。 初步分析 那么用非树边u代替树边t1，t2，t3中任意一条都可以得到一棵新的生成树。 而如果u的边权比所替换的边的边权更小的话，则可以得到一棵权值更小的生成树。 那么要使原生成树T是一棵最小生成树，必须满足条件： Dt1≤ Du ； Dt2≤ Du ； Dt3≤ Du 初步分析 如果边v，u(u可替换v)，则必须满足 Dv≤ Du ，否则用u替换v可得到一棵权值更小的生成树T-v+u 。 初步分析 不等式Dv≤Du中v总为树边，而u总为非树边。 那么显然树边的边权应该减小(或不变)，而非树边的边权则应该增大(或不变)。 设边权的修改量为Δ，即 Δe=|De－Ce| 当e∈T， Δe=Ce－De，即De=Ce－Δe 初步分析 那问题就是求出所有的Δ使其满足以上不等式且： 最小。 那么当u可替换v时，由不等式 观察此不等式 其中不等号右侧Cv－Cu是一个已知量！ 大家或许会发现这个不等式似曾相识! 这就是在求二分图最佳匹配的经典KM算法中不可或缺的一个不等式。 KM算法中，首先给二分图的每个顶点都设一个可行顶标，X结点i为li，Y结点j为rj。从始至终，边权为Wv,u的边(v,u)都需要满足lv + ru ≥Wv,u 。 我们来构造二分图G 建立两个互补的结点集合X，Y。 X结点i表示图G0中树边ai(ai∈T)。 X Y 设这些结点均为实点。 X Y 构造二分图G 如果图G0中，aj 可替换ai，且Ci－Cj0,则在X结点i和Y结点j之间添加边(i,j), 边权Wi,j=Ci－Cj。 X Y X Y 设这些边均为实边。 在结点数少的一侧添加虚结点，使得X结点和Y结点的数目相等。 构造二分图G X Y 如果X结点i和Y结点j之间没有边，则添加一条权值为0的虚边(i,j)。 构造二分图G X Y 算法分析 设完备匹配X的所有匹配边的权值和为SX，则 对于图G的任意一个完备匹配X，都有 设M为图G的最大权匹配，显然M也是完备匹配，则满足 显然，此时的可行顶标之和取到最小值。 因为虚结点Xi的匹配边肯定是权值为0的虚边，所以li=0。同理对于虚结点Yj，rj = 0。 显然，SM即是满足树T是图G0的一棵最小生成树的最小代价。那么问题就转化为求图G的最大权完备匹配M，即可用KM算法求解。 算法分析 问题解决 复杂度分析 我们来分析一下该算法的时间复杂度。 预处理的时间复杂度为O(|E|) KM算法的时间复杂度为O(|V||E|) 由于图G是二分完全图。 |V|=2max{n – 1, m – n + 1}=O(m) |E|=|V|2=O(m2) 所以算法总时间复杂度为O(m3) 。 用KM算法解此题在构图时添加了许多虚结点和虚边，但其并没有太多实际意义。 思考 那么，算法中是否存在大量冗余呢？还有没有优化的余地呢？ 下面就介绍一种更优秀的 算法！ 前面用KM算法解此题时构造了一个边上带有权值的二分图。其实不妨换一种思路，将权值由边转移到点上，或许会有新的发现。 匹配 算法分析 答案是肯定的，如果不添加这些虚结点和虚边，可以得到更好的算法。 同样建立两个互补的结点集合X，Y。 构造二分图G X结点i表示树边ai(ai∈T)， Y结点j表示任意边aj(aj∈V0)。