AcWing 861. 二分图的最大匹配
原题链接
简单
二分图的最大匹配
#include<bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e5+10;
int n1, n2, m;
int h[N], e[M], ne[M], idx;//注意N与M
int match[N];//右半边匹配的左半边为什么
bool st[N];//右半边是否已匹配
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool find(int x)
{
for(int i=h[x]; i!=-1; i=ne[i])
{
int j=e[i];
if(!st[j])
{
st[j] = true;
if(match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
int main()
{
cin>>n1>>n2>>m;
memset(h, -1, sizeof h);
for(int i=0; i<m; i++)
{
int u,v;
cin>>u>>v;
add(u,v);
}
int res=0;
for(int i=1; i<=n1; i++)
{
memset(st, false, sizeof st);
if(find(i)) res++;
}
cout<<res;
return 0;
}