二分图匹配：增广路、点覆盖与模型转化

二分图（Bipartite Graph）是图论中的基础模型，用于处理具有“二元对立”或“资源匹配”特征的网络结构。将复杂问题映射为二分图模型后，可以通过多项式时间复杂度的算法求得全局最优解。

一、二分图的物理本质与判定

定义：

若一个无向图的节点可以被划分为两个互不相交的集合 $A$ 和 $B$ ，且图中所有边的两端均分别属于集合 $A$ 和集合 $B$ （即同一集合内部没有任何边相连），则该图称为二分图。

核心推论（奇环定理）：

一个图是二分图，当且仅当它不存在长度为奇数的环。

证明逻辑：若从集合 $A$ 的某节点出发，经过奇数条边必然停留在集合 $B$ ，不可能回到起点。因此，含有奇环的图无法满足二分图的划分条件。

二分图：二染色与奇环定理

1. DFS 染色法判定

基于奇环定理，可使用 0 和 1 两种颜色对全图进行深度优先搜索（DFS）染色。遍历时，要求所有相邻节点的颜色必须相反。如果在染色过程中发现相邻节点已着色且颜色与当前节点冲突，则说明图中存在奇环。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

vector<int> node[N];
int color[N]; 

// DFS 染色判定：u 为当前节点，c 为当前应染的颜色
bool dfs_color(int u,int c){
	color[u]=c;
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i];
		if(color[v]==-1){
			if(!dfs_color(v,1-c)) return false;
		}else if(color[v]==c){
			return false; // 颜色冲突，存在奇环
		}
	}
	return true;
}

void solve_check(){
	int n,m;
	cin>>n>>m;
	memset(color,-1,sizeof color); 
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		node[u].push_back(v);
		node[v].push_back(u);
	}
	
	bool is_bipartite=true;
	for(int i=1;i<=n;i++){
		if(color[i]==-1){
			if(!dfs_color(i,0)){
				is_bipartite=false;
				break;
			}
		}
	}
	cout<<(is_bipartite?"YES":"NO")<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve_check();
	return 0;
}

DFS 染色：相邻节点必须颜色相反

二、最大匹配与匈牙利算法

场景：求二分图中包含边数最多的匹配集合，使得集合中的边没有任何公共端点。

1. 增广路机制

匈牙利算法的核心在于寻找增广路（Augmenting Path）。

当左部节点 $u$ 尝试匹配右部节点 $v$ 时：

若 $v$ 未被匹配，则直接建立匹配。
若 $v$ 已被匹配给左部的 $u'$ ，则算法会尝试让 $u'$ 去寻找其他可用的右部节点。若 $u'$ 能够成功“腾出位置”（递归寻找增广路），则 $u$ 即可接手 $v$ 。

2. 时间戳优化（常数优化）

在常规实现中，每次为左部节点寻找匹配前，需要使用 memset 清空 vis 数组以防止死循环，这会引入 $O(N)$ 的常数开销。

优化方案：在每次外层循环时传入当前节点的编号 $i$ 作为时间戳（tag）。内层判定时使用 if(vis[v] == tag)，即可实现 $O(1)$ 的状态重置。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;

vector<int> node[N];
int match[N]; 
int vis[N];   

// 匈牙利算法核心：tag 替代 memset 进行轮次标记
bool dfs(int u,int tag){
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i];
		if(vis[v]==tag) continue; 
		
		vis[v]=tag; 
		
		if(!match[v] || dfs(match[v],tag)){
			match[v]=u; 
			return true;
		}
	}
	return false; 
}

void solve_match(){
	int n,m,e; 
	cin>>n>>m>>e;
	for(int i=1;i<=e;i++){
		int u,v;
		cin>>u>>v;
		node[u].push_back(v); 
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		if(dfs(i,i)) ans++; 
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve_match();
	return 0;
}

匈牙利算法：增广路与时间戳优化

三、二分图模型转化定理 (König 定理及其推论)

在实际竞赛中，题目往往不会直接要求求解最大匹配，而是需要利用定理完成图论模型的等价转化。

1. 定理 1：最小点覆盖 = 最大匹配数

模型定义：在图中选取最少的节点，使得图中的每一条边都至少有一个端点被选中。
等价关系：二分图的最小点覆盖数，在数值上严格等于该图的最大匹配数。
典型应用：行列覆盖模型（如用最少的行和列覆盖矩阵中的所有目标点）。将行视作左部，列视作右部，坐标视为连边。

2. 定理 2：最大独立集 = 总节点数 - 最大匹配数

模型定义：在图中选取最多的节点，使得选出的节点之间互不相连。
等价关系：二分图的最大独立集大小 = 全图节点总数 - 最小点覆盖数（即最大匹配数）。
典型应用：约束共存问题（如棋盘放置互相不能攻击的棋子）。通常结合矩阵坐标特征建立二分图（如按 $x+y$ 的奇偶性划分左右部）。

3. 定理 3：有向无环图 (DAG) 最小路径覆盖 = 节点数 - 最大匹配数

模型定义：用最少的不相交的简单路径覆盖 DAG 中的所有节点。
等价关系：将 DAG 中的每个节点 $u$ 拆分为左部的“出点” $u$ 和右部的“入点” $u'$ 。原图中的边 $u \to v$ 映射为左 $u$ 连向右 $v'$ 的边。最小路径覆盖数 = 节点总数 - 该二分图的最大匹配数。

König 定理与二分图模型转化

四、构造点覆盖与独立集的真实方案

前面我们得出了“最小点覆盖 = 最大匹配数”以及“最大独立集 = 总节点数 - 最小点覆盖数”的数值关系。但在实际做题时，往往不仅要问“是多少”，还会要求“输出具体的选择方案”。我们如何把这些点挑出来？

1. 寻找最小点覆盖的交替路算法

推导过程：假设我们已经用匈牙利算法跑完了最大匹配。对于左部的节点，有些匹配成功了，有些落单了。

从左部所有未匹配的节点出发，沿着交替路（未匹配边 $\to$ 匹配边 $\to$ 未匹配边 $\dots$ ）进行标记。
因为这些起点本身是未匹配的，且图里已经没有增广路（否则就不是最大匹配了），所以这条交替路必然在右部的某个匹配节点终止，或者在左部的某个匹配节点停下。
选点规则：最后，挑选左部未被标记的节点，以及右部被标记的节点。它们构成的集合就是最小点覆盖！

直观例子：假设有左部 $L_1, L_2$ ，右部 $R_1, R_2$ 。边有： $(L_1, R_1), (L_2, R_1)$ 。跑完最大匹配后，匹配边只有 $(L_1, R_1)$ 。此时 $L_2$ 未匹配。从 $L_2$ 出发，走未匹配边到 $R_1$ ，从 $R_1$ 走匹配边回 $L_1$ 。标记了 $L_2, R_1, L_1$ 。按规则，取左部未标记（空集），右部标记（ $R_1$ ）。最小点覆盖是 $\{R_1\}$ ，确实只用 $R_1$ 就能覆盖所有边。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;

vector<int> node[N]; // 左部 u 连向右部 v
int match_r[N];      // 右部节点匹配的左部节点
int match_l[N];      // 左部节点匹配的右部节点 (方便找起点)
int vis[N];          // 匈牙利时间戳
bool vis_l[N], vis_r[N]; // 找方案时的标记数组

bool dfs(int u, int tag){
	for(int i=0; i<node[u].size(); i++){
		int v = node[u][i];
		if(vis[v] == tag) continue;
		vis[v] = tag;
		if(!match_r[v] || dfs(match_r[v], tag)){
			match_r[v] = u;
			match_l[u] = v; // 顺手记录左部的归属
			return true;
		}
	}
	return false;
}

// 找方案的 DFS：走交替路
void dfs_plan(int u){
	vis_l[u] = true;
	for(int i=0; i<node[u].size(); i++){
		int v = node[u][i];
		if(!vis_r[v]){
			vis_r[v] = true;
			// 顺着匹配边走回左部继续标记
			if(match_r[v]) dfs_plan(match_r[v]);
		}
	}
}

void solve(){
	int n, m, e; // 左部 n，右部 m，边数 e
	cin >> n >> m >> e;
	for(int i = 1; i <= e; i++){
		int u, v;
		cin >> u >> v;
		node[u].push_back(v);
	}
	
	// 1. 求最大匹配
	for(int i = 1; i <= n; i++){
		dfs(i, i);
	}
	
	// 2. 从左部未匹配点出发标记
	for(int i = 1; i <= n; i++){
		if(!match_l[i]) dfs_plan(i);
	}
	
	// 3. 收集结果
	vector<int> cover_l, cover_r;
	for(int i = 1; i <= n; i++) if(!vis_l[i]) cover_l.push_back(i);
	for(int i = 1; i <= m; i++) if(vis_r[i]) cover_r.push_back(i);
	
	cout << "最小点覆盖数: " << cover_l.size() + cover_r.size() << '\n';
	cout << "选取的左部点: ";
	for(int i=0; i<cover_l.size(); i++) cout << cover_l[i] << " ";
	cout << "\n选取的右部点: ";
	for(int i=0; i<cover_r.size(); i++) cout << cover_r[i] << " ";
	cout << '\n';
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

输入样例（范围：n,m <= 1000）：

对应输出样例：

最小点覆盖数: 2
选取的左部点: 1
选取的右部点: 1

左部 3 未匹配，从它出发能标记右部 1 和左部 2，最终选出 $\{L_1,R_1\}$ ，这次真正用到了交替路搜索。

2. 构造最大独立集方案

物理推导：独立集与点覆盖是天然“互补”的。我们在图中选走了一批点（最小点覆盖），这批点镇压了所有的边。那么剩下的点之间，绝对不可能有边相连（如果有，就说明刚才的点覆盖没覆盖完全）。因此，最大独立集的方案 = 全图所有节点 - 最小点覆盖选中的节点。

对应到上面的算法实现，独立集的节点就是：左部被标记的节点 + 右部未被标记的节点。

五、DAG 路径覆盖的方案恢复

先确认原图是 DAG；若还不熟悉判环与拓扑序，可回看《拓扑排序与 DAG 动态规划》第一、二节。

我们已经知道如何用拆点把 DAG 的最小不相交路径覆盖转化为二分图匹配。但怎么把这条链揪出来输出呢？

核心思路：在拆点的二分图匹配中，左部点 $u$ 和右部点 $v'$ 的匹配，在物理意义上就代表原 DAG 中选择了一条有向边 $u \to v$ 。这意味着，匹配不仅告诉我们“盖了几条路”，还顺手存下了前驱后继。右部数组 match_r[v] = u 记录了前驱，而在匈牙利算法中同步维护的左部数组 match_l[u] = v 则直接记录了“ $u$ 的下一步是 $v$ ”。

恢复路径的代码片段（紧接在最大匹配跑完后使用）：

// 数组依赖：需要先跑完二分图匹配，并维护好 match_l 数组表示左部匹配的右部点。
// 找所有路径的起点：如果一个左部点没有作为别人的终点（即对应的右部点未被匹配），它就是整条链的起点。
vector<int> in_degree(n + 1, 0);
for(int i = 1; i <= n; i++){
	if(match_l[i]) in_degree[match_l[i]]++; 
}

for(int i = 1; i <= n; i++){
	if(in_degree[i] == 0) { // i 是某条路径的起点
		int curr = i;
		while(curr) {
			cout << curr << " ";
			curr = match_l[curr]; // 顺藤摸瓜找下一步
		}
		cout << '\n';
	}
}

六、二分图匹配与单位容量网络流（选学）

本套讲义不展开网络流实现；本节先了解匹配与网络流的联系，已有网络流基础再继续。

匈牙利算法的时间复杂度是 $O(VE)$ ，对于 $N \le 1000$ 的题目游刃有余。但如果节点数达到 $10^4$ 到 $10^5$ 级别，匈牙利就会面临超时风险。这时候我们需要更高维度的先修武器：网络最大流。

1. 模型转化：把匹配变成水流

任意一个二分图匹配问题，都可以无损转化为网络流问题：

建立一个超级源点 $S$ ，向所有左部节点连一条容量为 $1$ 的有向边。
所有左部节点向对应的右部节点连一条容量为 $1$ 的有向边。
所有右部节点向超级汇点 $T$ 连一条容量为 $1$ 的有向边。

物理意义：容量为 $1$ 保证了每个左部点最多发出一条匹配边，每个右部点最多接受一条匹配边。网络跑出的最大流流量，精确等于二分图的最大匹配数。

2. 算法降维：Hopcroft-Karp 与 Dinic

如果在这个构造好的网络上跑 Dinic 算法，由于所有边的容量都是 $1$ （这种图被称为单位网络），Dinic 的时间复杂度会从理论的 $O(V^2E)$ 骤降到严格的 $O(E \sqrt{V})$ 。这使得我们能在一秒内处理十万级别的二分图匹配。

在图论中，专门用于二分图快速匹配的 Hopcroft-Karp 算法，其本质就是利用 BFS 寻找多条不相交的增广路，它与单位网络上的 Dinic 算法在底层思想和复杂度上是完全等价的。在竞赛实战中，面对大规模二分图，直接套用“超级源汇建图 + Dinic 模板”往往是最省心、最稳妥的选择。

七、渐进式实战练习题单

1. 基础判定与算法模板

洛谷 P1330 封锁阳光大学
- 考点：DFS 染色判定。
- 思路：将图划分为多个连通块。若某连通块满足二分图性质，则选取该连通块中被染为两种颜色的节点数较小的一方累加至总答案；若染色失败，则无解。
洛谷 P3386 【模板】二分图最大匹配
- 考点：匈牙利算法模板。
- 思路：重点练习基于时间戳 tag 的 vis 数组优化实现。

2. 模型映射与定理应用

洛谷 P1129 [ZJOI2007] 矩阵游戏
- 考点：完美匹配 / 行列模型映射。
- 思路：矩阵中黑格的存在表明其对应的行与列之间存在联系。无论如何交换行列，同行或同列的元素绑定关系不变。将行编号作为左部，列编号作为右部，若存在黑格 $(x, y)$ 则连接边 $x \to y$ 。若最大匹配数等于矩阵维度 $N$ ，则必然存在合法交换方案。
- 多测提醒：每组重新建图并清空 match；若时间戳仍从 1 开始，vis 也要清空，别让上一组的标记拦住这一组的搜索。也可以让 tag 跨组一直递增，这样 vis 就不用每组重置。
洛谷 P1640 [SCOI2010] 连续攻击游戏
- 考点：属性匹配与搜索序。
- 思路：将装备具有的两个属性值视为左部节点，装备本身视为右部节点。按 $1 \dots 10000$ 的顺序依次为属性值寻找可用装备（匹配），遇到首次无法匹配的属性值即可停止并输出结果。
- 模板迁移：右部是装备编号，match/vis 要按装备总数开；左部邻接表按属性范围开，别直接沿用 P3386 的 N=1005。时间戳写法可以继续用。
洛谷 P3355 骑士共存问题
- 考点：棋盘染色与最大独立集。
- 思路：利用棋盘横纵坐标之和的奇偶性，将未损坏的网格天然划分为二分图的左右两部。根据骑士的攻击规则建立冲突边。最终安全放置的最大数量即为该图的最大独立集。