二分图

二分图速通

定义

若一个无向图 \(G=(V,E)\) 的点集 \(V\) 可以分解成两个互不相交的子集 \(A,B\)，且对于所有边 \((i,j)\) 的端点 \(i,j\) 都分别属于子集 \(A,B\) 中的元素，则称 \(G\) 是一个二分图。

判定

一张无向图是二分图，当且仅当图中不存在奇环。

故我们有染色算法判定二分图：BFS 将每个顶点的相邻点都染成不同的颜色，若相邻点有相同颜色，则说明不是二分图。否则是二分图。

相关定义

匹配 或 独立边集：一张图中无公共点的边集合。

• 极大匹配：无法再增加匹配边的匹配，不一定是最大匹配。
• 最大匹配：匹配边数量最多的匹配，不一定唯一，但最大匹配的边数一定小于等于点数的一半。
• 最大权匹配：带权图中，边权和最大的匹配。
• 最大权最大匹配：所有最大匹配中边权和最大的匹配，即优先满足匹配边数量最多的前提下的最大权匹配。
• 完美匹配 或 完全匹配 或 完备匹配：所有点都属于匹配。易得此时符合最大匹配。若图是完全图且边数为偶数，必然存在完美匹配。
• 近完美匹配：点数为奇数的图中，除去一个点以外剩下的点符合完美匹配。

交错路：始于非匹配点且由匹配边和非匹配边交错而成的路径。

增广路：始于非匹配点、终于非匹配点的交错路。增广路中边的数量为奇数，且第一条边和最后一条边一定不属于匹配边。如果将增广路上的所有匹配边和非匹配边交换（取反），可以得到一个更大的匹配。

二分图最大匹配

核心思路

枚举所有未匹配点，找增广路，直到找不到增广路。

算法流程（匈牙利算法）

1965 年由匈牙利数学家 Edmonds 提出。

初始置 \(M\) 为空。每次找出一条增广路 \(P\)，通过取反操作找出更大的匹配 \(M'\) 代替 \(M\)，直到找不出增广路为止。时间复杂度 \(O(nm)\)。

具体地，每次考虑一个左部未匹配点，寻找一个右部点尝试与之匹配。一个右部点能被匹配当且仅当满足如下两条件之一：

1. 该点未匹配。
   此时直接把两个点匹配。
2. 该点之前匹配的左部点可以找到另一个右部点与之匹配。
   此时递归进入该左部点，为之寻找与之匹配的右部点。利用访问标记避免重复搜索。

实现（P3386 【模板】二分图最大匹配）

#include<bits/stdc++.h>
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;

char buf[1<<20],*p1=buf,*p2=buf;
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
constexpr int MAXN=1005;
int n,m,k,head[MAXN],tot;
struct{int v,to;}e[50005];
void addedge(int u,int v){
	e[++tot]={v,head[u]};
	head[u]=tot;
} 
int match[MAXN],ans;
bool vis[MAXN];

bool dfs(int u){
	for(int i=head[u];i;i=e[i].to){
		if(vis[e[i].v])continue;
		vis[e[i].v]=1;
		if(!match[e[i].v]||dfs(match[e[i].v]))
			return match[e[i].v]=u,1;
	}
	return 0;
}

int main(){
	n=read(),m=read(),k=read();
	for(int i=1,u,v;i<=k;++i){
		u=read(),v=read();
		addedge(u,v);
	}
	for(int i=1;i<=n;++i){
		memset(vis,0,sizeof(bool)*(n+m+5));
		ans+=dfs(i);
	}
	printf("%d\n",ans);
	return 0;
}