二分图的最大匹配（找妹子的游戏hh）

易错点
1.只需要存放左边指向右边的值
2.两个集合n1 n2 每次遍历n1， 注意第一行输入三个数
3.注意每个男生找的时候，都要清空上一个男生找的妹子。重复利用hh

思路：
月老的工作：

1.循环分析每个男生的情感问题： for(int i = 1; i <= n1; + +i)
2.先把每个找过的妹子清空（毕竟你找过了的妹子，我也可以再找）：memset(st, false, sizeof st)
3.判断每个男生能否找到妹子：find()
判断所有可能的妹子 ：for(int i = h[x]; i != -1; i = ne[i])
（找过的妹子没脸再找了。。）：if(!st[j])
如果妹子没有找到男生。或者妹子当前的男盆友能找到另外一个备选的(hh)妹子， 就是俺的了hh ：if(!match[j] || find(match[j]))
返回true， 找不到返回false
4.如果男生成功地找到妹子，答案+ + ：if(find(i)) res+ +;

样例

2 2 4
1 1
1 2
2 1
2 2

算法1

(匈牙利算法) $O(n+m)$

时间复杂度

参考文献

y总的人生哲学

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 100010;
int e[M], ne[M], h[N],idx;
int n1, match[N];
bool st[N];

void add(int a, int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] =idx++;
}
int 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] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof h);
    int n2 , a, b, res, k;
    cin >> n1 >> n2 >> k;
    while(k--)
    {
        cin >> a >> b;
        /*只从男生的角度来找就可以啦*/
        add(a, b);
    }
    for(int i = 1; i <= n1; ++i)
    {
        memset(st, false, sizeof st);
        if(find(i)) res++;
    }
    cout << res << endl;
    return 0;
}