lp3386 二分图最大匹配

一道匈牙利算法的模板题。
对于一张二分图\(G\)（也就是没有奇环的图），我们定义它的「匹配」为一个图\(G'(V’,E’)\)，使得：
$$\forall V” \in V’,V”_{u}\in E’,V”_{v}\in E’,|E’|=2|V’|$$
我们称一个匹配是最大匹配，当且仅当它是一个边数最多的匹配。

匈牙利算法是用于求解最大匹配的一类问题。
匈牙利算法使用了一种被称为「增广」的操作。
我们首先定义一条增广路径指的是一张二分图上的路径，使得这条路径的起点和终点都是尚未匹配的点，并且它的路径上经过的所有点都是已经匹配过的点。
那么很容易可以发现，一条增广路径上的边必然是「一条已匹配一条未匹配」的。
于是，我们对增广路径上的所有边的匹配状态取反，就可以增加匹配数量的大小。
增广操作是指，对于一个点，尝试访问它的每一个相邻点，然后从这个相邻点找下去，直到能找到一条增广路径为止。然后将这条增广路径上所有边匹配状态取反。
故而，每一次新加入一个点，我们尝试一次增广。这样就能够找到最大匹配了。

#include<iostream>
#include<cstdio>

int mp[1005][1005];
bool vis[1005];
int n,m,q,usd[1005];
inline bool dfs(int X){
	for(int i=1;i<=m;++i){
		if(!mp[X][i]){
			continue;
		}
		if(!vis[i]){
			vis[i]=1;
			if(!usd[i]||dfs(usd[i])){
				usd[i]=X;
				return 1;
			}
		}
	}
	
	return 0;
}
void init(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			mp[i][j]=mp[j][i]=0;
			usd[i]=usd[j]=0;
		}
	}
	int u,v;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&u,&v);
		if(u>n||v>m){
			continue;
		}
		++mp[u][v];
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		ans+=dfs(i);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}