AcWing 861. 二分图的最大匹配
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-19 17:07:19
,
所有人可见
,
阅读 290
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];
void add(int a , int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void init()
{
memset(h,-1,sizeof h);
}
int find(int x)
{
//枚举此男生看上的所有的妹子
for(int i = h[x] ; i != -1 ;i = ne[i])
{
int j = e[i];
//此时的这个妹子没有被考虑过, 如果考虑过了,此时就不需要重复来进行考虑
if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
{
st[j] = true;//那x就预定这个女孩了
//!match[j] 表示此妹子没有被男生进行匹配
//或者此时妹子被匹配的男生还是有别的妹子可以来进行预订的
//此时这个妹子就是可以空出来了。
if(!match[j]||find(match[j]))
{
match[j] = x;
return true;
}
}
}
//自己中意的全部都被预定了。配对失败。
return false;
}
int main()
{
init();
cin>>n1>>n2>>m;
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
}
int res = 0;
for(int i = 1; i <= n1 ;i ++)
{
//因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
memset(st,false,sizeof st);
//如果一个男生很成功的匹配到了一个女生。
if(find(i))
res++;
}
cout<<res<<endl;
}