AcWing 861. 二分图的最大匹配
原题链接
简单
作者:
术
,
2021-01-25 15:24:00
,
所有人可见
,
阅读 215
#include <iostream>
#include <cstring>
using namespace std;
int n1,n2,m;
const int N=505,M=100005;
int h[N],e[M],ne[M],idx;//只需要存单向图
bool st[N];//n2中的姑娘是否被在次循环考虑过
int match[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool dfs(int t){
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]){
st[j]=true;
if(!match[j]||dfs(match[j])){
match[j]=t;
return true;
}
}
}
return false;
}
int main()
{
cin>>n1>>n2>>m;
memset(h,-1,sizeof h);
for(int i=0 ;i<m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
int ans=0;
for(int i=1;i<=n1;i++){
memset(st,false,sizeof st);
if(dfs(i)) ans++;
}
cout<<ans<<endl;
//cout << "Hello world!" << endl;
return 0;
}