二分图

约定

• 如无特别说明，本文中的 \(n,m\) 分别为左右部点数，且总有 \(n\leqslant m\)。边集记为 \(E\)，边数记为 \(e\)。

定义

• 二分图是如下的一张图：

  • 可以将 \(V\) 划分为 \(V_1,V_2\) 使得 \(V_1,V_2\) 内部没有边。由此，二分图可以记为 \(G=\{V_1,E,V_2\}\)。

  • 可以黑白染色（可以染色指的是，存在一种染色方式，使得有边相连的两个点不同色）。

  • 不存在奇环。

  • 上述几个定义是等价的。

判定

• 建 dfs 树找奇环就好。

例题

• \(\text{P1525 [NOIP2010 提高组] 关押罪犯}\)

  • 略。

  • 值得一提的是，种族并查集也能做。事实上，种族并查集在一定意义上就是在“染色”。

  • 23.1.27 upd：这涉及到一些 2-SAT 相关，等以后整理。

• \(\text{P1155 双栈排序}\)

  • 题意：给一个排列，问能否通过两个栈使其单调递增。只允许使用入/出栈操作（出栈即输出）。如果可行，输出字典序最小的方案。

  • 数据范围：\(n\leqslant 10^3\)。

  • 首先我们知道任何时候较大数不能在较小数上方。换言之，如果 \(i<j,a_i<a_j\)，那么 \(j\) 不能和 \(i\) 放在同一个栈里。

  • 所以我们将 \(i,j\) 连一条边表示矛盾——错了。当且仅当 \(i\) 没有出栈，上面的限制是一条矛盾边。

  • 故加一个条件：\(\exists k>j,a_k<a_i\)，从而 \(i\) 一定不能出栈。

  • 好了，暴力建图尝试黑白染色，\(O(n^2)\)。方案显然很好总归可以构造。

匹配

• 对于 \(G=\{V,E\}\)，匹配 \(M\) 指的是一个边集 \(E'\)，其中的边彼此没有公共端点。

• \(|M|\) 最大即边数最多的匹配称为最大匹配。

• \(\sum\limits_{e\in M} v_e\) 最大即权总和最大的匹配称为最大权匹配。

• 匹配中的边称为匹配边，反之为未匹配边。

• 完美匹配：如果有 \(|V_1|\leqslant |V_2|\ \And\ |M|=|V_1|\)，那么 \(M\) 是 \(G\) 的完美匹配。

增广路与匈牙利算法

• 增广路：若 \(P\) 是图 \(G\) 中一条连通两个未匹配点的路径，且路径上属 \(M\) 的边和不属 \(M\) 的边交替出现，则称 \(P\) 为相对匹配 \(M\) 的一条增广路，也称增广轨或交错轨。

• 从定义出发，我们可以看出增广路具有如下性质：

  • 路径长度必为奇数，第一条和最后一条边都不属于 \(M\)。

  • 对 \(P\) 上的匹配边和非匹配边取反可以得到一个更大的匹配 \(M'\)。

  • \(M\) 为 \(G\) 的最大匹配当且仅当不存在相对 \(M\) 的增广路。

  • 增广路的本质是带悔贪心。

• 匈牙利算法：从每个点出发依次增广。时间复杂度为单轮增广 \(O(e)\)，总复杂度 \(O(n\times e)\)，故令 \(n\leqslant m\) 是有益的。下面给出一种基于递归的代码实现。

bitset<maxn> vis;
int match[maxn];//match[x]=y 表示的是右部的 x 配左部的 y。 
il bool hung(int now){
	for(ri int to:e[now])
		if(!vis[to]){
			vis[to]=1;
			if(!match[to] || hung(match[to])){
				match[to]=now;
				return 1;
			}
		}
	return 0;
}

• 代码细节：

  • \(now\) 总是左部点。即使对应的 \(to\) 已经有匹配，我们也是尝试着去递归那个 \(match\)。

  • \(match\) 的下标是右部点，内容是左部点。\(vis\) 记录的是右部点的访问情况，显然访问过的没有再访问的必要。

  • 显然记录左部点的 \(vis\) 没有意义，因为一个左部点被访问当且仅当它是 \(match\)，显然它只能是一个点的 \(match\)。

  • 匈牙利算法退环境了，复杂度太高。现在版本强势的是网络流求二分图最大匹配，\(O(\sqrt{n}e)\)，再不然是 HK(Hopcroft-Karp)算法，也是 \(O(\sqrt{n}e)\)。

例题

• \(\text{P1640 连续攻击游戏}\)

  • 题意：\(m\) 件装备打 \(n\) 层护甲（只能按从外向里即编号递增的顺序打），每件装备能且仅能打破某两层护甲，每件装备只能使用一次。问最多能打破几层护甲。

  • 数据范围：\(n\leqslant 10^4,m\leqslant 10^6\)。

  • 显然是二分图。我们给出增广路的一个性质：匹配点不会因增广而失配。

  • 所以可以直接无脑依次增广。边数太多？边数多就意味着图很稠密，从而匈牙利算法的复杂度远远达不到上界。严谨地讲，匈牙利算法的复杂度是单轮增广 \(\Omega(1)\sim O(m)\)，而非 \(\Theta(m)\)。

• \(\text{HDU1281 棋盘游戏}\)

  • 题意：给定一幅 \(n\times n\) 的棋盘，有些点不能放车（但是车可以通过）。

    • （1）求最多能放几个车，使得它们不互相攻击。

    • （2）如果想要放下最多的车，有多少个点是绕不开的，即，有多少个点必须放车？

    • （3）将不能放车的点改为不仅不能放车，而且车不能通过。请将上面两个问题再回答一遍。

  • 数据范围：\(n\leqslant 100\)。

  • 乍一看非常想搜，因为这个问题长得很像 \(\text{P1896 [SCOI2005] 互不侵犯}\) 和 \(\text{P1219 [USACO1.5]八皇后问题}\)（对后者的题目名称做了改动使更符合印象）。

  • 但是，两者的数据范围分别是 \(n\leqslant 9\) 和 \(n\leqslant 13\)。显然，车没有比后更特殊的性质，所以多半会 T，更不用说还要求方案限制。

  • 大脑升级一下，总之就是使劲想，我们会发现，一辆车会占领一行和一列，一行+一列恰好是两个元素。

  • 所以将行、列分别视为左右部点，每个能放车的点是一条边，发现每个点所连的边只能有一条生效，换言之，每个点只能和一个与它有边的点匹配。

  • 所求的最多车又恰好可以转化成最大生效边数，从而问题转化成最大匹配，\(O(n\times e),e\to n^2\)。

  • 下面考虑怎么求关键点（棋盘上的），或者说“关键车”。

  • 模仿求桥的思路，先随便求一个最大匹配，所有不在该匹配中的边都肯定不是关键边。

  • 依次拆掉这一最大匹配中的边跑匈牙利算法，则只用做 \(|M|\to 2n\) 遍，满图也不 T。

  • 第三问显然就是把行/列变成被障碍堵住的广义行/广义列就行了。

  • 第三问在拆边跑增广的时候可能会 T？是的，有可能，那个的匹配数可能很大。不过：

    • 可以设法重复利用信息。每次跑出来的新最大匹配，如果大小足够大，那么将它与已有的关键边取交集。这一操作可能可以，至少在随机数据下一定可以大大减小拆边次数。

    • 匈牙利算法的复杂度是 \(O\)。可以考虑拆那条边的时候不从头开始跑，而是将它对应的 \(match\) 改掉，然后对着那个已有 \(|M|-1\) 的匹配跑，平均数据下应该也能加速不少。

    • 这第三问本来就是某老年咸鱼教练乱嘴的，关我什么事？

  • 有一个（炎国粗口）在打这道题的时候把匈牙利算法板子打错了。警钟敲烂。

• \(\text{TYVJ1035 棋盘覆盖}\)（这个 OJ 已经寄掉了，这道题做不了）

  • 题意：一个 \(n\times n\) 的棋盘，有些地方是障碍，最多能放多少个 \(1\times 2\) 的骨牌（骨牌可以旋转）？

  • 数据范围：\(n\leqslant 100\)。

  • 发现基本和上一题一样，骨牌所在的两个点构成一组矛盾关系。并发现棋盘显然可以相邻黑白染色。故易解。复杂度 \(O(n\times e),e\to n^2-2n\)，显然不 T。

Hall 定理

• 对于二分图 \(G=\{V_1,E,V_2\}\)，不妨令 \(|V_1|\leqslant |V_2|\)，则当且仅当 \(\forall W\subseteq V_1,|N(W)|\geqslant |W|\)，对应二分图有完美匹配。其中 \(N(W)\) 是（\(V_2\) 中）与 \(W\) 中点有边的点集。

  • 必要性：假设对应条件不成立而存在完美匹配，取出一个使该定理不成立的集合 \(W\)，因为 \(|W|>|N(W)|\)，\(V_2\) 中点一定不够。

  • 充分性：用增广路证的。

    • 假设对应条件成立而对应二分图没有完美匹配，考虑取出一个最大匹配，易得至少有一个点 \(u\in V_1\) 没有匹配，定义其所在的单元素集为 \(U\)。

    • 则 \(|N(U)|\geqslant 1\)，且其中元素一定有匹配。从而从 \(u\) 开始跑交错路径树，最后每个叶节点一定都在 \(V_1\) 一侧（否则存在增广路，与对应匹配是最大匹配的预设矛盾）。

    • 此时将左部访问过的所有点记为 \(S\)，将右部访问过的点记为 \(T\)，易得 \(S>T\)（因为 \(u\) 的存在），与原条件成立的预设矛盾。

• 推论：二分图的最大匹配大小为 \(V_1-\max(|W|-|N(W)|)\)，这里 \(W\) 可以为 \(\varnothing\)。

  • 证明：不会，自行感性理解一下吧。大概就是，某个集合内部的冲突程度。

例题

• \(\text{HDU6667 Roundgod and Milk Tea}\)

  • 题意：有 \(n\) 个班，每个班有 \(a_i\) 人，制造 \(b_i\) 杯奶茶。每个人不喝自己班的奶茶，而且至多喝 \(1\) 杯奶茶。问最多能让多少人喝到奶茶。

  • 数据范围：

    • \(T\leqslant 25\)。

    • \(n\leqslant 10^6,\sum n\leqslant 6\times 10^6\)。

    • \(a_i,b_i\leqslant 10^9\)。

  • 乍一看想到匹配，但是 \(10^6\) 的范围怎么看都不太可能吧？虽然边很密集，但是网络流的 \(O(n\sqrt{e})\) 看着都没希望，匈牙利岂不是 T 飞？

  • 直接贪？显然不对吧？顺序是什么呢，或者说，多个可行选择的话，选哪个呢？如果带悔的话岂不是又退化成增广了，把班级缩成点也不太可行啊（没有 \(a_i=a_j\) 或 \(b_i=b_j\) 的保障啊）？

  • 考虑运用 Hall 定理（没有特殊说明的话，都指推论）。众所周知，裸的 Hall 定理是指数复杂度，所以有一个常见的操作：

  • 在 \(|N(W)|\) 不变的前提下，极大化 \(|W|\)。这可以让我们快速地卡到那个限制最大匹配的真正下界，而略过其他茫茫多的不关键子集。

  • 回到本题，考虑把学生作为左部点，奶茶作为右部点（其实都一样），则对于一个 \(N\)，我们做如下的分类讨论：

    • \(N=\varnothing\)：\(|W|-|N(W)|=0\)，实际含义即 \(|M|\leqslant \sum a\)。

    • \(N\) 中所有学生都来自同一个班级：显然，将 \(N\) 极大化为 \(a_i\) 对 \(|N(W)|\) 无影响。又容易用前后缀和求得 \(|N(W)|\)，从而此时 \(|W|-|N(W)|=a_i-\sum\limits_{j\neq i} b_j\)。

    • \(N\) 中所有学生来自至少两个班级：此时 \(N(W)\) 显然等于 \(V_2\)，故不妨将 \(N\) 极大化为 \(\sum a\)，从而 \(|W|-|N(W)|=\sum a-\sum b\)。化简可以发现，实际含义是 \(|M|\leqslant \sum b\)。

  • 发现实际上只需要暴力枚举每个班做第二种情况就好了。\(O(n)\)。

• \(\text{AT2645 [ARC076D] Exhausted?}\)

  • 题意：给定一个二分图，左部 \(n\)，右部 \(m\) 个点，对于 \(i\in V_1\)，\(i\) 与 \([1,l_i]\cup[r_i,m]\subseteq V_2\) 连边。求最大匹配。

  • 数据范围：\(n,m\leqslant 10^5,l_i<r_i\)。

  • 裸的 Hall 定理显然是指数函数的复杂度，想点别的办法。

  • 鉴于这是经典的双关键字问题，考虑对第一关键字排序，将问题转化为有第一关键字个阶段的单关键字问题。

  • 将人按照 \(l_i\) 单调不降排序。

  • 先取出第一个人，此时 \(N(W)=[1,l_1]\cup[r_1,m]\)。考虑在不改变 \(N(W)\) 的前提下极大化 \(|W|\)。

  • 发现对于所有 \(l_i\leqslant l_1 \And r_i\geqslant r_1\) 的人，他们可以无代价增大 \(|W|\)。但这样暴力枚举还是太慢了。

  • 考虑只暴力枚举 \(L\)，将所有 \(l_i\leqslant L\) 的点插入到线段树上 \(r_i\) 处，线段树上每个节点 \(k\) 都对应着一个固定的 \(N(W)=[1,L]\cup[k,m]\)，\(|W|\) 为插入的后缀和。

  • 取它们中的 \(\max(|W|-|N(W)|)\)。容易证明，总复杂度为 \(O(n\log m)\)。

点覆盖

• 图 \(G=\{V,E\}\) 的点覆盖指的是一个点集 \(V'\)，使得任何一条边都有至少一个端点 \(\in V'\)。

• \(|V'|\) 最小即点数最少的点覆盖称为最小点覆盖。

• 二分图中，最小点覆盖的点数=最大匹配的匹配数。证明如下（记一个可能的最小点覆盖为 \(V'\)，可能的最大匹配为 \(M\)）：

  • 首先，\(|V'|\geqslant |M|\)，否则，一定存在某条匹配边的两个端点都不在最小点覆盖内。

  • 接下来我们证明一定存在至少一个 \(|V'|=|M|\) 的构造方案。

  • 取任意的最大匹配，选中所有匹配边的右点（即 \(\in V_2\) 的点，下同）。显然，这样有 \(|V'|=|M|\)。

  • 这样的方案一定是一个合法点覆盖，证明如下：

    • 假设存在一条边的两个端点都不属于 \(V'\)，显然这条边一定不是匹配边。

    • 由最大匹配的定义，两者一定至少有一个为匹配点，而右点不可能是匹配点，否则它被选中。故左点为匹配点。

    • 从这个右点开始跑交错路径树，最后经过的边一定都是匹配边，即最后回到右部。从而改为选左部的所有匹配点，问题解决。

    • 更具体地说，如果这种翻转不可行，那一定是某条交错路径停留在左部（最后经过的是非匹配边），这样一来把选中右部改为选中左部后，那条路径的最后一条边没有覆盖。

    • 但这样的情况违背最大匹配的定义：它有增广路。

例题

• \(\text{HDU1150 任务安排}\)

  • 题意：

    • 有两台机器，\(A\) 机器有 \(n\) 种模式，\(B\) 机器有 \(m\) 种。可以花费 \(1\) 的代价将 \(A\) 或 \(B\) 的模式切换成任意的一种模式。

    • 有 \(K\) 个任务，第 \(i\) 个任务要么是让 \(x_i\) 模式的 \(A\) 机器完成，要么是让 \(y_i\) 模式的 \(B\) 机器完成。任务可以以任意顺序完成。

    • 求完成所有任务的最小代价。

  • 数据范围：\(n,m\leqslant 100,K\leqslant 1000\)。实际上可以做 \(n,m\leqslant 550,k\to n\times m\)。

  • 把状态视为左右部点，任务视为边，则显然这是最小点覆盖的板子。

路径覆盖

• 图 \(G=\{V,E\}\) 的路径覆盖指的是一个路径集 \(P\)，使得 \(\forall v\in V,\exists p\in P,s.t.v\in p\)。即任何一个点都在某条路径上。

  • 这里的路径是广义路径，即单点也被认为是一条路径。

• \(|P|\) 最小的路径覆盖称为最小路径覆盖。我们下面主要研究有向图的最小路径覆盖，因为无向图可以把边翻倍转化成有向图。

• DAG 的不相交最小路径覆盖：

  • 考察所有路径，发现一个事情：每个点只能做一次起点，做一次终点，换言之，出入度都不超过 \(1\)。

  • 不妨先认为 \(|P|=n\)，即每个点都用单点来覆盖。

  • 考虑选一条边的影响，发现选中后以 \(s\) 为终点的路径和以 \(e\) 为起点的路径可以合成一条路径，代价 \(-1\)。

  • 于是想到（鬼知道怎么想得到）将一个点作为起点和作为终点对立起来，建二分图，左部是作为终点的 \(i\)，右部是作为起点的 \(i\)。

  • 每条有向边都是这个二分图上的一条边。每个点作为起点/终点都只能连一条边（否则路径相交了）。每选一条二分图上的边，代价 \(-1\)。

  • 于是答案就是 \(n-|M|\)，其中 \(M\) 为对应二分图的最大匹配。

• DAG 的可相交最小路径覆盖：

  • 此时的主要问题在于，每个点可以有多个入度和出度。

  • 于是有一个很妙的转化：考虑求出 \(ava_{i,j}\) 表示从 \(i\) 到 \(j\) 可不可达，即用原图的传递闭包代替其边集。以 \(ava\) 为参考建二分图，然后故技重施。

  • 正确性证明：

    • 首先我们知道，同一个点可以不发出超过一条路径。

    • 如果有，可以做如下调整：第一条以后的路径都把起点后移到路径上第一个没有覆盖过的点上。

    • 同理，一个点可以不作为多条路径的结尾。所以这个最小路径覆盖可以套最大匹配的模型。

    • 此时考虑每一条路径，其上没有相交冲突的边显然可以直接用（在二分图中选进匹配），有冲突的边可以“跳过”，即选一条包括它的路径来规避掉冲突影响。更具体地，二分图上的边所对应的并非原图的边，而是将原图上两条路径“合并”的操作，可相交意义下相当于和传递闭包相对应。

    • 综上，这是对的。

例题

• \(\text{HDU1151 Air Raid}\)

  • 题意：给定一张 \(n\) 点 \(m\) 边的 DAG，可以在任意的地方降落伞兵，伞兵走过的地方（包括降落的地方）会被控制。不允许两个伞兵走过同一个点。问最少降落多少个伞兵可以控制全图。

  • 数据范围：\(n\leqslant 120,m\to n^2\)。

  • 板子。

独立集

• 对于图 \(G=\{V,E\}\)，独立集指的是一个点集 \(V'\)，使得 \(\forall i,j\in V',\nexists edge_{i\to j}\)。

• \(|V'|\) 最大的独立集称为最大独立集。

• 二分图中，\(|V'|=n-|M|\)，其中 \(V'\) 为最大独立集，\(M\) 为最大匹配。给出两个版本的证明：

  • 基于点覆盖：由前，最小点覆盖大小=最大匹配大小。删去最小点覆盖后，其他点之间一定不存在边，否则与点覆盖的定义矛盾。

  • 基于交错路径：

    • 考察 \(M\) 的每一个极大的交错路径树（可能是图？），这里的交错路径应当以匹配边开头和结尾。

    • 可以证明，不在该交错路径树中而又和其中的点有边的点一定都是左部点或都是右部点，否则存在增广路。

    • 从而一定存在一种方案，可以在这些非交错路径树点都选上后，恰选每条匹配边的两个端点之一。事实上，就是选和那些非交错路径树点同侧的匹配点。

    • 则显然只有 \(|M|\) 个点没有选上。

例题

• \(\text{P5030 长脖子鹿放置}\)

  • 题意：

    • 在一个 \(n\times m\) 的棋盘上放置长脖子鹿，有些点不许放。

    • 问在不存在任何两个长脖子鹿互相攻击的前提下，最多能放多少个。

    • 长脖子鹿的移动规则是 \(\pm(\pm 3,\pm1)\) 和 \(\pm(\pm 1,\pm3)\)。或者可以认为是把马的攻击范围推远一格。

  • 数据范围：\(n,m\leqslant 200\)。

  • 考虑转化成二分图，但是发现所在点和可达点同色。怎么办？

  • 按我们的需要去染色！发现每次移动，横/纵坐标的奇偶性一定变化。选一个按奇偶性染色就好。

  • 于是是板子。

例题选讲

• \(\text{CF1105E Helping Hiasat}\)

  • 题意：你有 \(m\) 个好友。现在有 \(n\) 次事件，按顺序发生，可能为你修改了 id 或者某个好友看了你的 id。如果某个好友每次看都发现你和他 id 一样，那么他会高兴，问最多能有多少个好友高兴。

  • 数据范围：\(n\leqslant 10^5,m\leqslant 40\)。

  • 发现相邻两次修改操作之间来访问的朋友一定矛盾。于是建图，建完之后...求最大独立集...嗯...

  • 这是个一般图！求解一般图的最大独立集是 NP 困难的，换言之，目前没有多项式时间算法。何解？

  • 看到 \(m\leqslant 40\)，考虑折半。

  • 分别暴力枚举前后一半朋友的所有子集，发现大概可以乱搞 \(O(2^\frac{n}{2}\times \frac{n}{2})\) 地判断是不是独立集。

  • 取出左边的所有独立集，右边跑反集子集和，权值即为点数，\(O(2^\frac{n}{2}\times \frac{n}{2})\)。

  • 显然有哪些不能拼也是很可做的事情。