二分图最大匹配

以下参考自https://blog.csdn.net/pi9nc/article/details/11848327

交替路:从未批配点出发,依次经过非匹配边,匹配边,非匹配边...形成的路径叫交替路.

增广路：从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路.增广路非匹配边比匹配边多一条,原因:由交替路的性质可得未匹配点一定在路的终点,且最后一条边为为匹配边.

Code:

(n1,n2为两个集合的点数,m为边数,1<=u<=n1,1<=v<=n2)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#define ll long long
#define rint register int 
using namespace std;
const int MAXN=1e6+10;
inline int in()
{
	int x=0,flag=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') flag=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*flag;
}
int n1,n2,m,nume,ans;
int head[1010],matchu[1010],matchv[1010];
bool vis[1010];
struct Edge
{
	int nex,to;
}adj[MAXN*2];
void addedge(int from,int to)
{
	adj[++nume]=(Edge){head[from],to};
	head[from]=nume;
}
bool dfs(int u)
{
	for (int i=head[u];i;i=adj[i].nex)
	{
		int v=adj[i].to;
		if (!vis[v])
		{
			vis[v]=true;
			if (!matchv[v]||dfs(matchv[v]))
			//未匹配;或match[v]已有增广路 
			{
				matchu[u]=v;
				matchv[v]=u;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	n1=in();n2=in();m=in();
	for (rint i=1;i<=m;i++)
	{
		int u=in(),v=in();
		if (u<=n1&&v<=n2)
			addedge(u,v); //注意
	}
	for (rint i=1;i<=n1;i++)
	{
		if (!matchu[i])
		{
			memset(vis,false,sizeof vis); 
			if (dfs(i)) ans++;
		}
	
	}
	cout<<ans;
	return 0;
}