Java教程

【模板】二分图最大匹配

本文主要是介绍【模板】二分图最大匹配，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【模板】二分图最大匹配
采用了匈牙利算法，时间复杂度为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;
}
这篇关于【模板】二分图最大匹配的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航