二分图系列

· · 个人记录

可能会不定期update

二分图定义

顾名思义，所谓二分图就是一个无向图的所有节点可以分成两个非空集合，集合内没有边相连，仅在两个集合之间有边相连。两个集合分别称为二分图的左部和右部。根据定义容易辨识出下图就是一个二分图。

二分图判定

定理：一张无向图是二分图，当且仅当图中不存在长度为奇数的环。

感性理解一下，二分图中的边都横跨左右两部，如果出现奇环就意味着必定有至少一条边连接了同一部中的两个点，与二分图的定义相矛盾。

根据该定理我们可以用染色法对二分图进行判定，规定左边的点都为颜色1，右边的点都为颜色2，也即一条边的两个端点颜色必须不同。执行DFS，对当前节点通过一条边所能到达的所有节点染成与当前节点不同的颜色，如果这些节点中有某个已经被染过色且其颜色与当前节点颜色相同，说明产生冲突，该图不是二分图。

bool dfs(int p,int col){
    vis[p]=col;
    for(auto y:l[p]){
        if(!vis[y]){
            if(dfs(y,3-col)) return 1;
        }else if(vis[y]==col) return 1;
    }
    return 0;
}

二分图匹配

二分图最大匹配

考虑一个边集，如果其中任意两条边都没有公共端点，则该集合称为图的一组匹配。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

增广路：二分图中，一条连接两个非匹配点的路径，使得匹配边与非匹配边在路径上交替出现，那么这就是一条增广路。

增广路具有以下性质。

1 .长度为奇数。

2 .第奇数条边是非匹配边，第偶数条边是匹配边。

基于以上性质，如果我们把增广路上的边全部取反，即非匹配边变匹配边，匹配边变非匹配边，那么可以得到一组新的匹配，并且匹配中的边数增加了1。

进一步的，当二分图的一组匹配不存在增广路，那么它一定就是二分图最大匹配了。

因此，考虑从寻找增广路入手来寻找最大匹配。

匈牙利算法

该算法的基本步骤如下：

1.初始所有边都是非匹配边

2.从每个左部点出发进行DFS尝试寻找一条增广路，对于右部匹配点标记与它匹配的左部点。如果找到，更新路径上所有右部点的匹配标记（让它与当前更优的左部点匹配），并让最大匹配答案加1。

如何寻找和判断增广路？

先来看看代码。

bool dfs(int p){
    for(auto y:l[p]){
        if(!vis[y]){
            vis[y]=1;
            if(!match[y]||dfs(match[y])){//这里
                match[y]=p;//匹配标记
                return 1;
            }
        }
    }
    return 0;
}

//以下加在主函数中，ans为最大匹配边数

for(int i=1;i<=n;i++) if(dfs(i)){
        memset(vis,0,sizeof(vis));
        ans++;
    }

可以注意到，上面代码的关键在于标注的if语句。

首先，如果从当前左部点出发直接找到一个未匹配的右部点，显然可以让最大匹配增加1，因为我们每次从新的左部点开始，所以这个左部点也一定没有匹配。

否则，如果这个右部点已匹配，那么我们从与之匹配的那个左部点开始再执行上述DFS过程，一直往上跑，如果在某个曾匹配过的左部点u处出发找到了一个没匹配的右部点v，那么我们就重新匹配，让u,v匹配，回溯时令每个遍历到的右部点与来时的左部点匹配，也即可找到一组更优的边数大1的匹配。

这样，我们就能在O(nm)的时间内求出二分图最大匹配。

网络流解法

请参见网络流系列。如果使用Dinic算法，时间复杂度将不会超过O(m \sqrt{n})，相对更优。但在代码实现方面，匈牙利算法更加简洁。

典例与建模分析

当我们遇到什么样的问题，可以转化为二分图匹配来解决呢？二分图匹配模型往往具有以下两种要素：

1.题目中的元素（节点）可分成两个独立集合，集合内部没有联系（不连边）。

2 .每个节点只能与一条匹配边相连。

对于题目中的一些特殊限制，可能可以转换成上述性质。来看一道例题：ACWing372棋盘覆盖

首先，对于骨牌的形状，考虑采用一种常用方法，对棋盘也即网格进行黑白染色，具体的，令行号加列号是奇数的为白色，是偶数的为黑色，这样保证了任意两个相邻格子颜色都不相同，那么一个骨牌显然只能覆盖两个颜色不同的格子。把白色格子作为左部点，黑色格子作为右部点，骨牌作为两个黑白格子之间的连边。同色格子之间没有连边，对应骨牌只能覆盖一黑一白；若令一个点只能被一条边相连，则恰好对应骨牌不能重叠，一个格子最多被覆盖一次；希望尽量多的放置骨牌，就是求上述二分图的最大匹配。

如此，我们完成了转化，直接套用模版即可。

事实上，类似的大多数题目都需要此种转化，将具体的问题抽象出来考虑。应用一些特殊的定理，还可以使得不同种类的问题转化成等价的同一类解法，这在二分图和网络流中尤为常见。具体的会在下面阐述。

二分图完备匹配

对于一张二分图，若左右节点数相同，均为N个节点，且最大匹配包含N条匹配边，则称该二分图具有完备匹配。了解即可。

二分图多重匹配

在此前的模型中，一个点最多只能与一条匹配边相连。如果现在节点i最多可以与k_i条边相连，再求最多选多少条匹配边，就变成了二分图多重匹配。多重匹配问题的解决方案并不唯一，这里暂时提供两种方法。

1.二分图上拆点。既然一个点i可以与k_i条匹配边相连，那么我们干脆把这个点拆成k_i个点，原问题等价于拆过之后的每个点最多与一条匹配边相连，直接跑二分图最大匹配即可。注意拆点时对节点重新编号。事实上，这种拆点技巧很多时候都会用到。

2.网络流解法。这种方法相对更加通用和高效，将在网络流系列中介绍。

放一道例题：P10936导弹防御塔。运用拆点技巧，与二分结合，有一定细节。

二分图带权匹配

略。参见网络流系列。
上面几种模型本质上差别不大。利用匈牙利算法大多都可以解决问题，关键在于模型的建立和转化。

二分图覆盖与独立集

二分图最小点覆盖

对于一张给定的二分图，求一个最小的点集，使得图中任意一条边都至少有一个端点属于该点集，这就是二分图的最小点覆盖。

定理： 二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。

该定理想一想会感觉非常合理，具体证明过程略，但它较为重要。利用这个定理，我们用求二分图最大匹配时的算法即可解决二分图最小点覆盖的问题，实现流程是一样的。下面通过一道例题来看二分图最小点覆盖的建模要素。

例：[USACO05JAN] Muddy Fields G

在二分图最大匹配的模型中，我们介绍了两种要素，在二分图最小点覆盖中，也有一个特点：每条边有两个端点，二者至少选择一个。在题目里，这对应着一个元素在两种选择中务必要加入至少一种选择。常令要被选择的元素作为连边，不同的选择作为点，这样就能转化成在二分图上求点覆盖的问题。

分析一下题意，发现每块泥地(i,j)要么被第i行一块横着的木板覆盖，要么被第j列一块竖着的木板覆盖，于是我们给每块木板编号，在每块泥地所属的横竖两块木板之间连边，这样一条边至少有一个端点被选择，也就意味着每块泥地至少被横竖木板中的一个所覆盖，刚好吻合题意，因此跑一遍二分图最小覆盖即可。

二分图最大独立集

对于一张无向图，一个任意两点之间都没有边相连的点集，称为这张图的独立集。包含点数最多的独立集就是最大独立集。

定理： 一张包含N个节点的二分图，其最大独立集大小等于N减去最大匹配数。

证明过程较为简洁。选出最多的点构成独立集，等价于在图中去掉最少的点（以及从他们出发的边），使剩下的点之间没有连边，也就等价于用最少的点覆盖所有边。用最少的点覆盖所有边，就是二分图的最小点覆盖。在上面我们曾提到，最小点覆盖数等于最大匹配数。因此总点数减去最大匹配数就是最大独立集包含点数。

上述三种概念互相转化的关系，一定要牢记。当遇到题目时，要从题目特征入手，归纳出题目的特性，比如哪些元素可以作为点，哪些条件可以作为边，点边各自表示什么，点和边怎样建立联系，以及要求的量怎样转化为图上问题等等。必要时要利用演草纸。

当然，截至目前我们讨论的都仅限于二分图上。在做题时要先判断模型是否满足二分图的条件，或如何转化成二分图。

有向无环图的最小路径点覆盖问题

可参见算阶和这篇博客。

对一张有向无环图用尽量少的不相交的简单路径覆盖所有顶点，称为最小路径覆盖。给出一条定理：有向无环图最小路径点覆盖包含的路径条数等于总点数减去拆点二分图的最大匹配数。证明见上述博客。例题：UVA1184 Air Raid（172已过，lg被spj卡了）

如果把上述条件改为可相交，其他不变，问题变成最小路径可重复点覆盖。对原图做传递闭包，即可转化成没有路径相交的点覆盖（见下图）。例题：P10938 Vani和Cl2捉迷藏

（上图有误，交点为p。。。）

总结：一些技巧与注意事项

1.二分图方面概念和定理比较多，注意不要混淆。这里进行一个汇总，方便查阅：

2.在二分图题目的模型转化中，一定要分清哪些是左部点，哪些是右部点，哪些作为边。一般来说，条件、代价或选择往往作为边，不同种类的元素往往作为点，这些元素可能包括但不限于行与列、选择者与被选择者、互相存在某种关系的两个数值等等。在上面的建模分析中我们曾提到几个要素，要经常回顾。

3.在代码实现中，要注意给节点编号的过程，每个节点都要有属于自己的编号，否则会出现自环。这一点在实现给平面图编号或拆点时要尤其注意。如果给平面图编号，可以借助行和列；如果拆点，可以让一类点统一加上某个量，或一类点乘2，一类点乘2再减1等等，只要保证不冲突即可。

3.要分清最小路径点覆盖和最小路径可重复点覆盖。只有可重复时才需要传递闭包。

4.由于二分图经常要额外增加点，因此数组一定要开够，不要看到题目数据范围中是多少就开多少。同时，在 for 循环扫的时候看看是扫到n还是2 \times n还是别的什么。

5.二分图类的题目，往往复杂在建图方面，其他基本都是板子。建图时能简洁就简洁，必要时可以调用函数，尽量别一股脑塞 for 循环里，写完你根本不想调它。

6.vis数组要在 for 循环里清空，如果多测，别忘了清空match数组。

7.其他的等我想起来再补吧。。。