D25 二分图最大匹配 匈牙利算法

/*
【参考程序】
最大二分匹配（匈牙利算法）：最后得到ans（最大匹配数）和match数组（match[y]表示母牛y的匹配对象的公牛编号）
数据结构：
int match[11100], chw[11100], tsp;
match数组是描述母牛的，chw数组也是描述母牛的。
tsp为时间戳（timestamp），记录当前主函数中那只公牛发起找母牛的
chw[y]是否等于tsp，表示母牛y在当前这轮找母牛活动中有没被询问过

算法过程：
1、在主函数中，让每只公牛去找母牛匹配，即发起n1轮找母牛活动，tsp记录当前是第几轮。
2、dfs(x)过程：
公牛x遍历每只它喜欢的母牛y。
如果y被询问过了chw[y]==tsp，则忽略(否则会造成程序死循环)；
如果y没被询问过chw[y]!=tsp，则：
    （1）、y还没有匹配（match[y]==0），那么直接匹配成功“match[y]=x；return 1;”
    （2）、如果y已经有成功匹配的对象了，那么尝试让y的匹配对象xx(设xx等于match[y])去找其它母牛匹配。如果xx成功找到其它母牛匹配，那么y就可以和x匹配。
    注意：xx去找其它母牛的过程是个漫长且复杂的dfs()递归过程。
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
vector<int> G[N];
int match[N], chw[N], tsp;
bool dfs(int x)
{
    for(int y : G[x])
    {
        if(chw[y] != tsp)
        {
            chw[y] = tsp;
            if( (match[y] == 0) || (dfs(match[y]) == 1) )
            {
                match[y] = x;
                return 1; // 匹配成功
            }
        }
    }
    return 0; // 匹配失败
}
int main()
{
    int n1, n2, m; scanf("%d%d%d", &n1, &n2, &m);
    for(int i=1, x, y; i<=m; i++)
    {
        scanf("%d%d", &x, &y);
        G[x].emplace_back(y);
    }
    int ans = 0;
    memset(match, 0, sizeof(match));
    memset(chw, 0, sizeof(chw));
    for(int i=1; i<=n1; i++)
    {
        tsp = i; // tsp记录当前是第i轮找母牛的活动
        if(dfs(i)) ans++;
    }
    printf("%d", ans);
    return 0;
}