【模板】二分图最大匹配
采用了匈牙利算法,时间复杂度为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;
}