二分图的最大匹配

匈牙利算法

二分图定义：
把一个图分成两部分，左右半部分内没有边，左边的每一个点都和右边的某一个点存在一条边

这里讲述继续采用课堂的娱乐化讲法（男女配对，好吧，我就是为了省事）

图的存储

因为我们匹配是从左向右匹配的，也就是每次从男生看向女生，所以存边存左边到右边的就行

因为要遍历临边是稠密图，推荐邻接矩阵（y总这里写的邻接表，代码好写一点，也可以）

算法流程

$1.$ 对于任何一个男孩（对于每一个左半部的点执行$find$操作）

$2.$ 依次看看和他相互有好感值的女生（遍历它的临边）, 如果在当前这个男生还没有考虑过这个女生(没有判断是否可以配对)，
$(1)$ 如果女生还没有找到配对的男生（$match$[ ]为0），那么好，他们可以凑成一对

$(2)$ 如果女生找到了配对的男生（$match$[ ]不为0），那么我们看看那个男生可不可以换一个女生配对，给当前这个男生一个机会，如果原来配对的男生可以换一个下家（递归尝试原来配对的男生），那么当前这个女生就和当前的男生进行配对

通过以上步骤，我们就可以让这么多男生女生里面获得最多的人成双成对（也就是达到二分图的最大匹配）

代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx; //邻接表存储
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()
{
    scanf("%d%d%d", &n1, &n2, &m);

    memset(h, -1, sizeof h); // 邻接表的初始化

    while (m -- ) 
    // 存边，存有向图就可以达到效果了。男生考虑女生，或者女生考虑男生都可以得到正确答案
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    int res = 0;
    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, false, sizeof st); // 考虑情况是每一轮对于当前男生的，所以之前的考虑数据要清空
        if (find(i)) res ++ ; // 匹配成功计数加一
    }

    printf("%d\n", res);

    return 0;
}