【模板】二分图最大匹配

【模板】二分图最大匹配
采用了匈牙利算法,时间复杂度为n*e+m

#include <bits/stdc++.h>
using namespace std;
const int MAX=505;
int n,m,e;
int g[MAX][MAX],lft[MAX];
bool vis[MAX];

bool dfs(int s) {
	for (int i=1;i<=m;i++) 
		if (g[s][i]&&!vis[i]) {
			vis[i]=true;
			if (lft[i]==0||dfs(lft[i])) {
				lft[i]=s;
				return 1;
			}
		}
	return 0;
}

int main() {
	int ans=0;
	cin>>n>>m>>e;
	for (int i=1;i<=e;i++) {
		int x,y;
		cin>>x>>y;
		g[x][y]=true;
	}
	for (int i=1;i<=n;i++) {
		memset(vis,false,sizeof(vis));
		ans+=dfs(i);
	}
	cout<<ans<<endl;
	return 0;
} 
上一篇:实验:Keepalived + Nginx + Tomcat 搭建高可用主从模式Web服务器


下一篇:拼接平方数