二分图（二部图）

概念：可分为两个集合，集合内的点无边相连的图

判定：染色法

int col[MAXN];
vector<int> ed[MAXN];
bool bfs(){
	col[1] = 1;
	queue<int> qu;
	while(!qu.empty()){
		int u = qu.front();
		qu.pop();
		for(auto v:ed[u]){
			if(!col[v]){
				col[v] = 2 - col[u];
				qu.push(v);
			}else if(col[v] == col[u])
				return 0;
		}
	}
	return 1;
}

无权二部图最大匹配问题

• 匹配：每个节点都只连一条边的边集合

转换为最大流问题

• 设置一个起点，连接集合S的所有点，权值为1，设置一个终点，连接集合T的所有点，权值为1，求最大匹配等价于求起点到终点的最大流

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 20,MAXE = 5e4 + MAXN;
#define inf 0x3f3f3f3f
struct edge{
	int v,w;
	int i;
	edge* nex;
}ed[MAXE*2];
edge* head[MAXN];
int ptop = 0;
void add(int u,int v){
	ed[ptop].v = v;
	ed[ptop].w = 1;
	ed[ptop].nex = head[u];
	head[u] = &ed[ptop];
	ed[ptop].i = ptop;
	ptop++;
	ed[ptop].v = u;
	ed[ptop].w = 0;
	ed[ptop].nex = head[v];
	head[v] = &ed[ptop];
	ed[ptop].i = ptop;
	ptop++;
}
int d[MAXN];
int s = 0,t;
bool bfs(){
	queue<int> qu;
	qu.push(s);
	memset(d,-1,sizeof(d));
	d[s] = 0;
	while(!qu.empty()){
		int u = qu.front();
		qu.pop();
		edge* p = head[u];
		while(p != NULL){
			int v = p -> v;
			if(p -> w && d[v] == -1){
				d[v] = d[u] + 1;
				qu.push(v);
			}
			p = p -> nex;
		}
	}
	if(d[t] == -1)
		return 0;
	else
		return 1;
}
int dfs(int u,int flow){
	edge* p = head[u];
	if(u == t)
		return flow;
	int use = 0;
	while(p != NULL){
		int v = p -> v;
		if(d[v] == d[u] + 1 && p -> w){
			int tem = dfs(v,min(flow,p -> w));
			use += tem;
			flow -= tem;
			ed[p -> i].w -= tem;
			ed[(p -> i)^1].w += tem;
			if(flow == 0)
				break;
		}
		p = p -> nex;
	}
	if(use == 0)
		d[u] = -1;
	return use;
}
int dinic(){
	int ans = 0;
	while(bfs()){
		ans += dfs(s,inf);
	}
	return ans;
}
int main()
{
	int n,m,e;cin >> n >> m >> e;
	for(int i = 1;i <= n;i++)
		add(s,i);
	t = n + m + 1;
	for(int i = 1 + n;i < t;i++)
		add(i,t);
	for(int i = 1;i <= e;i++)
	{
		int u,v;cin >> u >> v;
		v += n;
		add(u,v);
	}
	cout << dinic();
}