二分图

二分图 JSOI2006 二 分 图 江苏省扬州中学 张煜承 摘要 二分图是一个特殊的图论模型。本文从二分图的定义和特点开始分析，探讨了二分图的最大 匹配、最小覆盖、最大独立集和最佳匹配的基本性质和相关算法。在此基础上，分析了近几 年与之相关的信息学竞赛题，并尝试以网络流为基础给出了常用算法。 关键字 二分图 匹配 覆盖 独立集 1. 定义 二分图 设 是一个无向图。如果结点集V 可分割为两个互不相交的子集 和 ， 使得 ),( EVG = 1V 2V E中每条边的两个结点，一个在 中，另一个在 中，则称 为二分图。 1V 2V G 二分图可以记为 ),,( 21 EVVG = 。 2. 二分图的最大匹配 2.1 定义 图的匹配 给定一个无向图 ，而),( EVG = M 是 E的子集，如果M 中的任两条边都没 有公共结点，则称M 是G的一个匹配。 可以看出图的匹配，实际上是在图的结点集中的两个不相交的子集间建立一一对应的关 系。而二分图 的匹配则是在 的一个子集和 的一个子集间建立一一 对应的关系。 ),,( 21 EVVG = 1V 2V 二分图的最大匹配 一个二分图的最大匹配就是它的所有匹配中边数最多的一个匹配。 2.2 求二分图的最大匹配数的方法 二分图的最大匹配可以转化成网络流问题。 首先把二分图中的边改成有向边，边的方向均为从 到 。然后增加一个源 和一个 汇 t。从源 到 中的每一个点连一条弧，从 的每一个点到汇 连一条弧。设定图中 的每一条边容量均为 1。接下来求从源 到汇 的最大流。 1V 2V s s 1V 2V t s t 这样求得的最大流量就是二分图的最大匹配数。 2.3 求匹配方案的方法 在求得从源 到汇 t的最大流后，检查网络中从 到 的每一条边e。若 的流量为 1，s 1V 2V e 第 1页 二分图 JSOI2006 则 ，否则 。 Me∈ Me∉ 2.4 举例 s t 5 时间复杂度分析 最基本的 Ford-Fulkerson 算法，即每次任意找一条增广路并沿 求方案需要在求得最大流的基础上，检查网络中的每条边。所以在求得最大匹配数后， 6 算法效率的优化 2.6.1 算法的实现 模型具有很多特殊性，所以在实现的时候，并不需要把整个网 6.2 贪心的应用 2. 如果求最大流时就使用 其增广，则最多增广 V次，每次增广需要 O(E)的时间，所以只求最大匹配数的时间复杂 度为 )(VEO 。 只要再花 O(E)的时间就可以求得最大匹配的方案。 2. 因为 )(VEO 对于很多题目来说太慢了，所以必须使用一些优化来加快速度。 因为转化成的网络流 络流算法都在程序中体现出来。比如说不需要记录所有边上的容量和当前的流量， 只要记录当前的匹配情况就行了。这样做虽然不能减小时间复杂度，但是可以使程 序略快一些。 2. s t 1 1 1 1 1 1 1 1 1 1 1 1 s 1 1 1 1 1 0 0 1 1 0 1 1 t 第 2页 二分图 JSOI2006 求最大匹配问题时，使用贪心往往只能求得一个较优解。但这个较优解通常都 是可 2.6.2.1 一个简单的贪心 左边的每一个结点。当枚举到一个结点v1时，枚举和 v1关 二重循环。并且显然这个贪心的时间 复杂 6.2.2 一个复杂的贪心 中度数最小的结点，然后找出和它相邻的度数最小的 结点 这个贪心的效果非常 好， 2.7 例题 乒乓球混合双打配对[JSOI2005 省队选拔] 双打队。现在知道每位男选手 析 为要对一些选手进行配对，所以可以自然地想到图的匹配。首先建立一个图， 图中 以注意到这些选手分为男选手和女选手，所以可以想到图中的结点可以分为 两类 算法的时间复杂度为 ，而 行解，所以，可以在这个可行的较优解的基础上使用网络流算法。这样做可以 非常有效地减小寻找增广路径的次数，从而大大减少网络流算法执行的时间。同时， 贪心通常都非常快，进行贪心的时间和网络流的时间相比通常可以忽略不计。这样 贪心可以有效地减小最大匹配的时间，而且贪心都比较容易实现。所以我建议在求 二分图的最大匹配时，尽量使用贪心。 下面介绍两种贪心。 按任意顺序枚举二分图 联的所有边，检查此边右边的结点现在是否已与其他结点匹配。如果还没有 与其它结点匹配，那么就让v1和它匹配。 这个贪心实现起来非常容易，只需一个 度是 O(N+M)。但是这个贪心的效果一般，所以我建议如果如果需要的效率 不高的话，每次求最大匹配都使用这个贪心。 2. 贪心时选择一个二分图 ，并让它们匹配。然后在二分图中删除这两个点及和它们相邻的所有边。 重复执行这一过程，直到图中没有边。为了使时间复杂度是 O(N+M)，实现的时 候需要用 N个链来维护每个可能的度数有哪些结点。 这个贪心实现起来相对复杂一些，需要用到链表。但是 对于一般的随机二分图，贪心之后，只要再执行大约 1 到 2 次增广路扩展， 就可以得到最大匹配。我建议只有当求二分图匹配需要的效率很高的时候，才 使用这种贪心。 例 1_1 有 M 位男选手和 N 位女选手要组成若干个乒乓球混合 可以和那些女选手配对。求一种方案，使得配出最多的混合双打对。 1≤M,N≤100 分 因 的结点为选手，边为选手间的关系，一条边表示它连接的两个结点可以进行配 对。那么这个图的匹配方案就对应于一个配对方案。要求配出最多的混合双打对， 就是要求匹配数最大。因此只需求得这个图的最大匹配，就可以直接得到答案。一 般图的最大匹配存在有效算法，但是实现起来往往比较复杂。我们再仔细地观察一 下。 可 。因为只能是一个男选手和一个女选手配对，不存在两个男选手配对或者是两 个女选手配对，也就是说同类结点间没有边。因此这个图实际上就是一个二分图。 所以我们要求的实际上是二分图的最大匹配。 于是就套用前面求二分图的最大匹配的算法。 )(VEO 第 3页 二分图 JSOI2006 数据规模为 1≤M,N≤100，不会超时。 例 1_2 多米诺骨牌[SGU190] 有一个 N×N 的正方形棋盘。棋盘上被挖掉 P 个方格。现在用 2×1 的多米诺骨牌来 覆盖剩下来的棋盘，骨牌不能重叠。问现在有没有可能把剩下来的棋盘全部覆盖， 如果有可能则输出一种方案。 1≤N≤40 分析 这道题目一开始看上去没有什么有效算法，似乎只能使用一些搜索之类的算法 解决。但是这道题目的数据规模是 1≤N≤40，这些算法肯定是会超时的。 观察一下题目，题目中用来覆盖的形状只有一种，即 2×1的长方形。这个形状 非常特殊，它恰好覆盖了两个相邻的方格。因为骨牌不能重叠，而且要求把剩下来 的方格全部覆盖，实际上就是把剩下来的方格全部分成若干个对子，使得每个对子 中的两个方格都是相邻的。而分对子，实际上就是把剩下来的方格进行一个匹配， 使得所有的剩下的方格都有另外的方格和它匹配。 于是建立一个图，以剩下来的方格为点，如果两个方格是相邻的就在它们对应 的结点间连一条边。因为要让所有的点都有另外的点和它匹配，所以我们需要求这 个图的最大匹配。如果最大匹配满足所有的点都有另外的点和它匹配，那么就可以 轻易的构造出一种覆盖方案。否则就不可能存在一种覆盖方案。和上题一样，这里 我们得到的是一般图的最大匹配，和上题一样，我们再进行一些思考，看看它是不 是一个二分图。 这个图中所有的边都是在两个相邻的格子对应的结点之间的，如果这个图是一 个二分图，那么应该可以找到一种分类方案，使得所有相邻的结点都在不同的类别 中。经过尝试可以找到如下图的所示的类似国际象棋棋盘的分类方案。于是这个图 可以判断为一个二分图。所以，与上题一样，我们要求的只是二分图的最大匹配。 建好图后，套用求二分图的最大匹配的算法，时间复杂度为 。因为在这 题中结点数是 ，而一个结点最多有 4条边和它关联，所以这题中的边数同样 是 ，因此总时间复杂度为 。而 N 最大是 40，不会超时。 )(VEO )( 2NO )( 2NO )()( 4NOVEO = 例 1_3 Unstable Systems[SGU218] 有 N 台计算机和 N 个软件。每台计算机要恰好运行一个不同的软件。给定每个软件 在每台计算机上运行的不稳定程度，求一个方案，使得最大的不稳定程度最小。 1≤N≤500 所有不稳定程度的绝对值不超过 1000000 第 4页 二分图 JSOI2006 分析 很容易可以看出这道题目是要在 N 台计算机和 N 个软件间建立一个一一对应的 关系。于是可以想到二分图匹配。首先建立一个二分图。图左边的结点表示计算机， 图右边的结点表示软件。然后在每一个计算机和每个软件之间连一条边。边的权值 代表这个软件在这个计算机上运行的不稳定程度。但是与前面两个题目不同，这道 题目并不是要求最大匹配，它的最大匹配数显然是 N。这道题目要求的是一个匹配 数为 N 的匹配，这个匹配中的最大边上的权值最小。 这个问题看起来比较难解决。所以我们先考虑这个问题的一个简化版本。由于 这个问题是一个最优化问题，所以可以考虑它所对应的一个判定性问题：给定一个 完全带权二分图，限定匹配中的所有边上的权值不大于 w，判断这个二分图有没有 一个匹配数是 N 的匹配。这个问题看起来仍然不太好解决。于是我们还要再分析一 下。 观察二分图中权值大于 w 的边，因为它们不能用来作匹配边，所以它们没有任 何作用，因此可以把它们全部去掉。去掉之后那个限制（限定匹配中的所有边上的 权值不大于 w ）就没有任何作用了，因此可以去掉。而且现在权值也没有用了，也 可以去掉。现在这个二分图就成了一个不带权的二分图。这样一来，问题就被简化 成了：判断这个二分图有没有一个匹配数是 N 的匹配。因为如果有这么一个匹配存 在的话，那么这个匹配一定是这个二分图的最大匹配。所以只要求这个二分图的最 大匹配就行了。于是这个简化问题就被解决了。 接下来回到原问题上。由于简化问题中需要知道匹配边的权值的限制。而这是 事先不知道的，只知道它在正负 1000000 之间。所以就可以想到二分这个值。经过 二分就可求得最大权值，从而也可以求到一个符合条件的匹配。因为最多做 次最大匹配（其中 R 表示最大边权值的范围），所以这样做的时间复杂度 为 。这个时间复杂度与边权的范围有关，所以这个算法不是真正的多 项式算法。 )(logRO )log( RVEO 进行一些观察，可以发现二分后最终的 w 一定是某一条边上的权值。所以 w 的 取值范围就可以缩小到所有边权所组成的集合。为了仍然可以用二分，可以先对所 有的边权值进行排序，形成一个序列，排完序后二分最大权值在此序列中的位置。 这样最多做 次最大匹配。所以后面二分的时间复杂度就降到了 。假设前面排序的时间复杂度为 ，那么总时间复杂度就是 。因为 1≤N≤500，所以这个题目可以算是解决了。 )(logEO )log( EVEO )log( EEO )log( EVEO 另外本题还有一个优化，可以使时间复杂度降到 O(VE)。因为在上面的解法中， 上次求得的最大匹配在下次求最大匹配时没有充分利用。因为上次求得的最大匹配 中的边可能到了以后就因为权值过大而不能用了。所以为了让上次求得的最大匹配 能够在下次求最大匹配时充分发挥作用，也就是在以后求最大匹配时上次的最大匹 配中的所有边仍然可以用，我们按照权值从小到大的顺序，把边加进去。在整个加 入的过程中，始终维护每个结点是否可以从源到达。加入一条边后更新当前的残留 网络，并更新每个结点是否可以从源到达。如果发现汇可以从源到达，那么就进行 第 5页 二分图 JSOI2006 增广，并重新用宽搜计算每个结点是否可以从源到达。增广了 V 次之后就立即停止。 此时的匹配即为所求。这样做每次增广的时间复杂度是 O(E)的，最多增广 V 次，所 以总时间复杂度为 O(VE)。 3. 二分图的最小覆盖 3.1 定义 图的覆盖 给定一个无向图 ，而 是V 的子集。如果),( EVG = C E中的每一条边都至少 和C中的一个点关联，则称C是无向图 ),( EVG = 的一个覆盖。 二分图的最小覆盖 一个二分图的最小覆盖就是它的所有覆盖中点数最小的一个覆盖。 对于一般的图，目前还没有找到求最小覆盖的多项式算法。但是二分图与一般的图相比 有很多特殊性。二分图的最小覆盖是可以很容易求到的。 3.2 求二分图的最小覆盖数的方法 首先给出一个定理。 定理 对于一个二分图 ，最小覆盖数等于最大匹配数。 ),,( 21 EVVG = 由这个定理，求最小覆盖数就转化成了求最大匹配数。求最大匹配数前面已经讲过了， 这里就不重复了。 3.3 求二分图最小覆盖方案的方法 用前面求最大匹配的方法建立流网络，求得最大流。求好了之后，检查最大流所对的残 留网络。从 s 开始做一次 floodfill，设所有访问到的结点组成的集合为 ，其他所有 的点组成的集合为 S T 。那么 )()( 21 SVTV ∩∪∩ 就是一个最小覆盖的方案。 3.4 举例 s 1 1 1 1 1 0 0 1 1 0 1 1 t s t 1 1 1 1 1 1 1 1 1 1 1 1 s 1 1 1 1 1 1 1 1 1 1 1 1 t 第 6页 二分图 JSOI2006 3.5 时间复杂度分析 如果只求二分图的最小覆盖数，那么时间复杂度显然和求最大匹配数的时间复杂度 一样。 如果还要求得一个最小覆盖的方案，只要在求得最大匹配的基础上，进行一次 floodfill 就行了。所以在上面的基础上再花 O(V+E)的时间就可以得到一个最小覆盖的 方案。 3.6 例题 例 2_1 任务安排[ACM/ICPC Regional Contest Beijing 2002] 有两台机器 A 和 B 及 N 个需要运行的任务。机器 A有 N 种模式，机器 B 有 M种模式。 他们初始时都处在第一个模式。每个任务 i 恰好在一台机器上运行。如果它在机器 A 上运行，则机器 A 需要设置为 模式，如果它在机器 B 上运行，则机器 B 需要设 置为 模式。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次 模式需要重新启动一次，请合理为每个任务安排一台机器，并合理安排顺序，使得 机器重启次数尽量少。 ia ib N,M<100 任务数量小于 1000 分析 首先研究一下怎么安排顺序最好。假如有一个任务可以在机器 A 或机器 B 的第 一个模式下执行。那么显然应该先让它执行，这样这个任务本身的代价就为零，而 且对其他的任务没有影响。所以这种任务和第一种模式可以在一开始的时候就去掉 不考虑。在下面讨论中我将不会考虑这种任务和第一种模式。再假如已经定下来机 器 A 要执行若干个任务，那么显然在机器 A 重启到另一个模式之前，把需要在当前 模式下执行的任务全部执行完最好。所以这个题目实际上就是要给机器 A 和机器 B 选择最少的模式，使得每个任务都可以执行。每个任务都执行也就是对于每个任务 i，机器 A 的 模式和机器 B 的 模式中至少要有一个被选中。 ia ib 这个问题和二分图的最小覆盖问题非常相似。这个问题是要求对于每个任务 i， 机器 A 的 模式和机器 B的 模式中至少要选一个。而最小覆盖问题是要求对于每 条边， 中的一个结点和 中的一个结点至少要选一个。并且两个问题都是要求选 择的数目最少。于是就想到将这道题目转化成二分图的最小覆盖来做。 ia ib 1V 2V 首先建立二分图。左边的结点表示机器 A 的各种模式，右边的结点表示机器 B 的各种模式。对于每个任务 i，在机器 A 的 模式所对应的结点和机器 B 的 模式 所对应的结点间连一条边。于是求得这个二分图的一个最小覆盖就可以构造出一种 最优执行方案。 ia ib 这样做的时间复杂度为 O(VE)，问题的规模为 N,M<100，任务数量小于 1000，所 以不会超时。 例 2_2 Asteroids[Usaco Nov06] 第 7页 二分图 JSOI2006 有 K 个小行星分布在一个 N×N 的网格中。有一种武器一次攻击可以将一行或者一列 的行星全部消灭。求最少需要多少次攻击才能将 K 个小行星全部消灭。 1≤N≤500 1≤K≤10000 分析 首先看看题目实际上是要求什么。因为这个武器攻击过一行或者一列后，这一 行或这一列的行星会被全部消灭，所以重复攻击是没有任何作用的。对于每一行和 每一列，需要选择是攻击还是不攻击，从而使得最后所有的行星全部消灭。问题要 求的就是要使选择的数目最少。 这个问题看起来不太好解决。于是换个角度，考虑每个行星。对于每个行星， 要使它被消灭，那么他所在的那一行和所在的那一列中就至少要有一个被选择。和 上题一样，由此可以联想到二分图的最小覆盖。 于是建立二分图。左边的结点表示所有的行，右边的节点表示所有的列。对于 每个行星，在他所在的行和所在的列之间连一条边。这样这个二分图的最小覆盖数 就是答案。 这样做的时间复杂度为 O(VE)，问题的规模为 1≤N≤500，1≤K≤10000，所以 不会超时。 例 2_3 Muddy Fields[Usaco Jan05] 有一块 R 行 C 列的田。田中有一些方格要用木板盖住，但其它方格不能用木板盖住。 木板宽为单位长度，长度任意。木板可以重叠。求最少需要多少木板。 1≤R≤50，1≤C≤50 分析 这道题目和上一道题目非常类似。题中用木板盖住方格可以认为是方格被武器 消灭。但是这道题目和上一题有一个不同的地方，就是上一题中武器可以一次打掉 一行或者一列的行星，而在这题中，因为存在不能覆盖的方格，木板可能无法覆盖 整行的方格。也就是说这题是上题的一个变形，多了障碍这个因素。 因为这题和上题非常类似，所以就在上题的算法的基础上进行修改。上题是选 择一些整行或一些整列，这题因为有障碍存在，所以需要选择一些被障碍分割后的 不连续的极长的横条或竖条。仿照上题，建立二分图，二分图左边的结点代表所有 的横条，右边的结点代表所有的竖条。对于每个要盖住的方格，在它所在的横条和 竖条间连一条边。然后仿照上题求这个二分图的最小覆盖数。这样做可以正确地求 得问题的答案。 因为图中的结点可能会很多，所以求最大匹配时需要加上贪心。 4. 二分图的最大独立集 4.1 定义 图的独立集 给定一个无向图 ),( EVG = ，而 是V 的子集。如果U 中任意两个点都不 相邻，则称U 是无向图 的一个独立集。 U ),( EVG = 二分图的最大独立集 一个二分图的最大独立集就是它的所有独立集中点数最多的一个 第 8页 二分图 JSOI2006 独立集。 4.2 求最大独立集的方法 要求二分图的最大独立集，只需先求得二分图的最小覆盖集，然后取它的补集即可。 4.3 举例 4.4 时间复杂度分析 与求二分图的最小覆盖集的时间复杂度相同。 4.5 例题 例 3_1 Knights[BOI2001] 一张大小为 N×N 的国际象棋棋盘，上面有一些格子被拿走了。你的任务是确定在这 个棋盘上放置尽可能多的马并使他们不互相攻击。 N≤200。 分析 因为这道题目的规模比较大，是 N≤200，所以简单的搜索、贪心等算法是不行 的。 下面考虑构图。因为题目中给的是棋盘，所以可以仿照前面多米诺骨牌那一题 进行构图。建立一个无向图，图中的结点代表剩下的方格。如果马可以在两个剩下 的方格之间直接到达，那么就在这两个方格间连一条边。这样，这道题目显然就是 求这个图的最大独立集。但是如果是一般的图，求最大独立集的多项式算法目前还 没有找到。所以，与前面的例子一样，考虑它是不是二分图。 经过思考，可以想到仿照前面的多米诺骨牌那题的染色方法对这道题目进行染 色。 X X X X S X X X X 染色之后，假设棋盘上有一个马，位置用 S 标出。它能攻击到的位置用 X 标出。 那么可以看出 S 所在的方格是灰色的，而所有 X 所在的方格是白色的。也就是说， 第 9页 二分图 JSOI2006 一个马只能攻击与它所在方格颜色不同的位置。所以图中的边的两个结点肯定颜色 相异。按照方格的颜色将所有的结点分成两类，这就是一个二分图。可以看出所求 的正是这个二分图的最大独立集。 套用前面的算法求这个二分图的最大独立集。时间复杂度是 O(VE)的，问题的规 模为 N≤200，不会超时。 5. 二分图的最佳匹配 5.1 定义 在定义最佳匹配前，首先定义完备匹配。其实这种匹配在前面的例子（例 1_2 多米诺骨 牌）中已经遇到过了。 完备匹配 给定一个满足 21 VV = 的二分图 ),,( 21 EVVG = ，而 M 是二分图 的一个匹配，如果),,( 21 EVVG = M 满足 21 VVM == ，那么称 M 是二分图 的一个完备匹配。 ),,( 21 EVVG = 如果一个二分图是加权完全二分图，所有权值非负，求权最大的完备匹配，这种匹配称 为最佳匹配。 5.2 转化成最大收益最大流做 首先把二分图中的边改成有向边，边的方向均为从 到 ，边上的收益均为原二分 图对应边上的权值。然后增加一个源 和一个汇 t。从源 到 中的每一个点连一条 弧，从 的每一个点到汇 连一条弧，收益设为 0。设定图中的每一条边容量均为 1。 接下来求从源 到汇 的最大收益最大流。求得的最大收益显然就是二分图的最佳匹 配中所有边的权值和。 1V 2V s s 1V 2V t s t 求匹配方案的方法 与求最大流的方案的方法类似，在求得从源 到汇 t的最大收益最大流后，检查网络 中从 到 的每一条边 。若 的流量为 1，则 s 1V 2V e e Me∈ ，否则 Me∉ 。 举例 2 3 1 5 2 3 1 5 2 3 1 5 0 0 0 0 0 0 1 1 2 3 1 5 1 1 1 1 第 10 页 二分图 JSOI2006 时间复杂度分析 时间复杂度取决于求最大收益最大流的时间复杂度。若用一般的不断求最长路的算 法，并且求最长路使用 Bellman-Ford 算法的变形，那么最大收益最大流的时间复杂 度为 )*( fVEO ，而 Vf =* ，所以求最佳匹配的时间复杂度为 。 如果求最长路使用 SPFA 的变形，那么最大收益最大流的时间复杂度平均为 )()( 42 VOEVO = )*( fEO ，求最佳匹配的时间复杂度平均为 。 )()( 3VOVEO = 5.3 求最佳匹配的 Kuhn-Munkres 算法（KM 算法）（注：为了方便描述，我这里给出的算 法与标准的 KM 算法在细节上有一定区别） 首先给出两个定义 可行顶标 对于二分图 ，设),,( 21 EVVG = 21 VVV ∪= ，如果映射 满足对 于任何的 RVl →: 21 , VyVx ∈∈ 有 ),()()( yxwylxl ≥+ 成立，则称 是二分图G 的可行 标号。 )(vl 相 等 子 图 定 义 一 个 可 行 定 标 对 应 的 相 等 子 图 为)(vl )},()()(,),(|),{( yxwylxlEyxyxEl =+∈= 。可以看出实际上相等子图就是把 左右结点标号等于权值的边全部抽出来。 KM 算法主要基于一个定理：一个可行标号对应的相等子图的一个完备匹配一定是原 带权二分图的最佳匹配。它利用了调整的思想：首先设定一个初始的可行标号。然 后不断循环，如果它的相等子图没有完备匹配，就用一种方法调整可行标号，使得 可行标号所对的相等子图的最大匹配数严格增大。这样一直循环下去，直到有完备 匹配为止。 框架 设定一个初始的可行标号; While (当前可行标号的相等子图没有完备匹配) 调整可行标号，使得可行标号的相等子图的最大匹配数严格增大; 细节 初始的标号：左边的结点的标号设为与这个这个结点关联的所有边的最大权值。右 边的结点的标号全部设为 0。 标号的调整：为了方便描述，假设求最大匹配的时候使用网络流。设最大流所对的 残留网络中从 s 开始进行 floodfill 所能访问到的所有点所组成的集合为 ，其余 所有点所组成的集合为 S T 。 首先求出标号调整的幅度大小 { }),()()(min 21 , yxwylxla TVySVxl −+= ∩∈∩∈ 。然 后对于 中的所有点标号减小 ，对于SV ∩1 la SV ∩2 中的所有点标号增加 。可以la 第 11 页 二分图 JSOI2006 证明按照这种方法调整了之后标号仍然是可行标号，原来相等子图中的所有匹配边 仍然保留，而且经过增广后必定会有新的匹配边产生。 举例 间复杂度分析 整结点标号，标号所对的相等子图的最大匹配数必定严格增加， 而最大匹配数显然就是 V，所以调整最多进行 次。而每次调整只需 次， 所以调整所用的时间是 。 V，而无效找增广路径的次数是 O(V)（即上述 每次找增广路径需要 的时间，所以匹配所花的时间也是 。 所以总时间复杂度为 。 终标号的性质 时 调整：由于每次调 )(VO )( 2VO 匹配：因为有效的找增广路径次数为 )( 3VO 框架中外层循环的次数，也就是调整最多进行的次数），所以共找 )(VO 次增广路径。 )()( 2VOEVO =+ )( 3VO )( 3VO 最 因为结点标号始终是可行标号，所以根据定义，对于任何的 21 , XyXx ∈∈ 必定有 成立。而且可以证明对于任何的),()()( yxwylxl ≥+ 21 XXx ∪∈ ，必定有 成立。 实际上，最终标号还有一个更重要的性质，即：在满足上述条件下 的值最小。 0)( ≥xl ∑ )(xl 2 3 1 5 2 3 1 5 5 3 0 0 5 3 0 0 5 3 0 0 5 3 0 0 s t 3 1 0 2 3 1 0 2 2 3 1 5 第 12 页 二分图 JSOI2006 这个性质在有些题目中有重要作用。 KM 算法的扩展 因为标准的 KM 算法只适用于满足|V1|=|V2|的所有权值非负的完全二分图的最 是一种非常特殊的情况。 0000，使得选择 n 条这样的边最后的权 值和 。 5.4 果只要求匹配的话，这两种算法总体上效果都差不多。但是 KM 算法有一个优势，就 很好的性质。 例 4_1 丘比特的烦恼[CTSC2000] 男子和 N 个女子。已知他们互相之间的的缘分值。求一种配对方案，使得每 大。 首先主要到这个题目的 N 非常小，最大才 30。所以可以考虑一些搜索、贪心之 法。但是不能保证在规定时间内求得最优解。 一个二分图，左边的结点表 示所 6. 求最小路 6.1 义 的简单路径覆盖有向无环图 G 的所有结点。 首先考虑一些简单的算法。 可以求得最优解，如果加一些剪枝优化，对于小规模的数据应该可以很快出 解。 时间复杂度还是指数级的，所以当数据规模很大的时 候很 大权匹配，而这 当原图中的一条边或一个点不存在时，可以将这条边或这个点加入，并设定后 加的边的权值为一个非常小的数，如：-100 总比选择 n-1 条这样的边最后的权值和小。 如果要求一个满足|V1|=|V2|的完全二分图的最小权匹配，就把每条边的权值 w 都改成-w。 当原图中有权值为负数时，就在所有的边权值上加上一个足够大的数，使得所 有的权值非负 两种算法的比较 如 是它最终的标号有一些 5.5 例题 有 N 个 一对被射中的人之间的缘分的和最 N<30 分析 类的算 因为是求一种配对方案，而且每个男子和每个女子都要有人和他配对，所以这 题是求 N 个男子和 N 个女子的一种完备匹配。于是建立 有的男子，右边的结点表示所有的女子。在每个男子对应的结点和每个女子对 应的结点间连一条边，边的权值为他们之间的缘分值。题目中要求缘分的和最大， 就是要求这个二分图的一个完备匹配的边权值之和最大。这个显然就是二分图的最 佳匹配问题。于是可以直接套用 KM 算法或者使转化成网络流问题解决。 如果使用 KM 算法的话时间复杂度为 O(VE)，不会超时。 径覆盖 定 用尽量少的不相交 6.2 分析 搜索， 但是因为再怎么剪枝，搜索的 难在很短的时间内计算出来。 贪心，不能求得最优解。不过用多种贪心策略再加上随机化，可能可以求得不错的 第 13页 二分图 JSOI2006 较优解。但不管怎么样都不能保证可以求得最优解。 管进来的边，一个管出去的边， 从管 我们看看直接建立网络流模型可不可以。由于每一个结点都要被覆盖且仅被覆盖到 一次，所以很容易想到把每个结点拆成两个结点，一个 进的点到管出的点之间连一条弧，流量上下界都设为 1。把原图中的边改造。由于 原图是无向图，所以，对于任何的 Eba ∈),( ，从 a 的管出的点到 b 的管进的点引一条 弧，从 b 的管出的点到 a 的管进的点 0，上界为 1。然后简单地 汇引一条弧，容量下界为 0，上界为 1。然后求这个流网络的最小流就行了。这个算法 是可行的，可以解决这个问题。 下面介绍一种更好的方法。观察每个结点，可以发现每个结点都恰好在一条简单路 径上。除了在路径的末尾的点没有 引一条弧，容量下界为 加一个源，加一个汇。从源到原图每个点管进的点引一条弧，从原图每个点管出的点到 后继外，所有的点都有唯一的后继。除了在一条路径 的开 路径 的条 在 这个二分图的最大匹配，假设最大匹配数是 原图的结点数是 路径数就是 。 只包 有要求的路径的图。从图中不断地取出极长的路径就可以得到方 案。 例 6.4 例题 例 5_1 三子棋[JSOI2005 Spring] 始的点没有前趋外，所有的点都有唯一的前趋。如果这把每个点都拆成两个点，一 个管进，一个管出，那么可以看出一个路径方案实际上就是二分图的一个匹配。 再来看看最佳方案的特征。要求的最佳方案是路径的条数最少。因为路径上的总边 数等于有后继的结点的总数，而路径条数等于没有后继的结点的总数，所以实际上 数+路径的总长度=图中的结点数。因此最佳方案的路径总长度是最长的，那么它所 对应的匹配大小就是最大的。现在就可以看出实际上就是要求一个二分图的最大匹配。 于是我们建立二分图模型。把原图中的所有点 i拆成 1i 和 2i ，其中 1i 在二分图的左边， 2i 二分图的右边。对于原图的每一条有向边 ),( ba ，在 分 中插入 ),( 21 ba 。然后求 mn − 求一个路径覆盖的方案很简单。把二分图中的每对对应的点合并起来，并只保留匹 配边。这就是 含所 二 图 m， n，那么需要的最少的 6.3 举 1 2 3 4 1 1' 2 3 4 2' 3' 1 1' 4' 2 2' 3 4 3' 4' 1 2 3 4 第 14 页 二分图 JSOI2006 有一种三子棋：在 3×3的棋盘上，先手画 x，后手画 o，交替行棋。给定一个残局， 局的所有子残局全部下到，并且每个子残局只 这个题目中有明显的状态，即棋盘上的每个格子中的情况，还有明显的状态间 ，即从一个状态开始再画一个 x 或者一个 o，可以到达另一个状态。不妨建 立一 杂度一般是 O(V 7. 综合 在解决一些难题时，二分图的有关知识有时需要和一些其他知识结合起来使用。 有一个 N 个结点，M 条边的带权无向图。给出这个无向图的一棵生成树。现在可以对这 些调整，即：可以给某条边的权值加上一个值，也可以减去一 首先，显然可以看出，如果一条边在给出的生成树上，那么它的权值只有可能减小， 的权值只有可能增加。 个最小生成树。这个问题的答案比较难看出。所以不妨从反面来看，即观察 如果 W(a)成立。也就是对于上面所说的边 求最少要下多少次棋，才能将给定残 能下到一次。 分析 的关系 个有向图，图中的结点表示状态，边就表示状态间的关系，边的方向表示状态 转移的方向。由于状态只可能从棋子少的状态转到棋子多的状态，所以这个图是无 环的。一次下棋实际上就是走图中的一条路径。所有子残局都要下到就是图中的每 个点都要走到。每个子残局只能下到一次就是指每个点只能走到一次，也就是所有 的路径都不想交。所以实际上问题就是求一个有向无环图中的最小路径覆盖。 于是首先用宽搜将给定残局的所有子残局全部列出来，同时确定它们之间的关 系。然后用上面讲过的方法求最小路径覆盖。求到的数就是答案了。 经过程序计算，在最坏情况下，即给定残局是一个空棋盘，构出的有向无环图 结点数目最多 5478 个，边数最多 16167 条。虽然求最大匹配的时间复 E)，但是实际所需的时间远远达不到这么多，因此只要使用一般的算法求二分图 的最大匹配就行了。 例题 例 6_1 Roads[SGU206] 个无向图上边的权值作一 个值，使得给定的生成树是新图的一个最小生成树。求一个调整方案，使得所有边的权 值修改量之和最小。 2≤N≤60，N-1≤M≤400 分析 否则它 设一条边 e加上或减小的值为 A(e)（A(e)≥0），原先的权值为 C(e)，最终改过的值 为 W(e)。 显然题目就是要求所有和最小的 A(e)。下面看函数 A 满足什么条件时给定的生成树 是新图的一 给定的生成树不是新图的一个最小生成树，那么函数 A 的值将会怎么样。如果给定 的生成树不是新图的一个最小生成树，那么一定可以找到一条在生成树外的边 a，将它 加入生成树，并在生成的一个环中找到另一条边 b，这条边的权值要大于边 a 的权值， 将它去掉，最终得到一棵更小的生成树。所以如果给定的生成树不是新图的一个最小生 成树，那么一定存在不在给定的生成树中的边 a 和在树中的边 b，使得边 a 加入生成树 后边 a 和边 b 在同一个环上，并且 W(b)>W(a)。 考虑原来的问题。如果要保证给定的生成树是新图的一个最小生成树，那么就要保 证对于所有上面所说的边 a 和边 b，都要有 W(b)≤ 第 15 页 二分图 JSOI2006 a 和 是两个变量的和，右边是一个常数。很容易可以联想到 KM 算 法结 一边 分图的结点数为O(E)。KM算法执行的时 间复 在一个 N×N 的棋盘上，有 M 个位置可以放車。要求它们互相不能攻击，那么可以计算 使得仍可以放下 k 个車。求 因为原问题比较复杂，所以先求出一个放最多車的方案。因为車互相之间不能攻击， 一行最多只能放一个車，每一列也最多只能放一个車。这就类似于二分图左右边 的每 网络流求最大匹配。设一条匹配边为(p,q)。如果在求得的最大流对应 的残 不在同一个 强连 边 b，都要有 C(b)-A(b)≤C(a)+A(a)成立。可以证明保证了这个不等式成立和上面 的 A(e)≥0 成立之后给定的生成树一定是新图的一个最小生成树。于是现在就是求一个 线性规划：在满足若干个形如 C(b)-A(b)≤C(a)+A(a)和形如 A(e)≥0 的不等式的条件下 使所有 A(e)的和最小。 把 C(b)-A(b)≤C(a)+A(a)进行一个移项处理，移项后不等式变成 A(a)+A(b)≥ C(b)-C(a)。不等式的左边 束后结点标号的性质，标号可以满足上面的这些限制，而且标号之和是最小的。 于是建立二分图。首先先尝试着把每一条边都加入进给定的最小生成树，并检查生 成的环上的边，由此建立不等式组。然后由这些不等式构造一个二分图。若二分图的某 少点，则在这一边补上少了的点。若某一条边不存在，则将它加入，并且设定权值 为 0。然后套用 KM 算法求出答案。 前面每次加入一条边之后，检查生成的环就用最简单的O(V)的算法。那么建不等式 组的时间复杂度就是O(VE)。由不等式建成的二 杂度就是O(E3)。因为E最大 400，所以这个算法可以解决问题。 例 6_2 棋盘上的问题[AHOI2006] 出最多可以放下 k 个車。现在从 M个位置中去掉一个位置， 可行的方案数。（注：输入数据中没有 k） 1≤N≤200000，1≤M≤600000 分析 所以每 一个结点都最多只能与一个匹配边关联。所以就考虑建立二分图匹配的模型来解决 这题。建立一个二分图，图左边的结点代表所有的行，图右边的结点代表所有的列。对 于每一个可以放車的位置，在它的行和列分别对应的结点之间连一条边。显然这个二分 图的一个匹配，就对应于一个合法的放車方案。于是求得这个二分图的最大匹配，就可 以得到放的車数最多的一个方案了。但是注意到问题的规模非常大，为 1≤N≤200000， 1≤M≤600000，只用一般的最大匹配算法是一定会超时的，所以必须要用一种很强的贪 心。在这道题目中，使用前面讲的那种复杂的贪心效果很好。 现在的问题就是要求这个二分图中有多少条这样的边，删除它之后，二分图的最大 匹配数不变。 显然求得最大匹配之后，这个二分图中所有的非匹配边都是满足要求的。下面考虑 匹配边。假设用 留网络上，反向边(q,p)在某一个有向环上，那么将这个环施加于最大流，这会保 证流量不变，就得到了(p,q)不是匹配边的最大匹配方案。可以证明任何一条满足题目 要求的匹配边一定在求得的最大匹配所对应的残留网络的某个有向环上。 那么现在就是要在求得的最大匹配所对应的残留网络中，快速地标记出所有环上的 边。一个方法就是先收缩强连通分量，然后对于每条边检查它两边的结点在 通分量中。如果在，这条边就一定在一个环上，否则，这条边就一定不在一个环上。 另一个更好的方法是类似求无向图的割点、桥的深搜。这两种方法都是利用 dfs，时间 复杂度都是线性的。因此这道题目就算是解决了。 第 16 页 二分图 JSOI2006 8. 总结 信息学奥赛中，问题的模型往往需要我们集中很大精力加以辨别，在图论模型中， 出的图是一个无向图，并且它满足结点集能够分成两个不相交的集合，而且所有 的边 化为求二分图的最大匹配。二分图的最小覆盖可以由一个定理转化为求二分图的 最大 参考 [1] 刘汝佳、黄亮 算法艺术与信息学竞赛 A. Brualdi Introductory Combinatorics on, Ronald L. Rivest, Clifford Stein. 如果建 的两个结点分别在这两个集合之中，那么我们就可以确定此模型为本文介绍的二分 图。 二分图的相关问题，大多可以转化为网络流来求解。与二分图有关的常见问题大多 可以转 匹配。二分图的最大独立集则和二分图的最小覆盖集互为补集，所以最终转化成求 二分图的最大匹配。二分图的最佳匹配可以用以二分图的最大匹配为基础的 KM 算法来 求解。一个有向无环图的最小路径覆盖经过拆点后也可以转化成二分图的最大匹配。 本文给出了一些与二分图有关的例题及其分析，希望能对大家以后做和二分图有关 的题目时有帮助。 资料 [2] Richard [3] Thomas H. Cormen, Charles E. Leisers Introduction to Algorithms. Second Edition. [4] 历年中国国家集训队论文 [5] 本文涉及的题目及其解题报告 第 17 页