洛谷P 3386【テンプレート】二分図ハンガリーアルゴリズムテンプレート二分図にマッチ

タイトルリンク:
https://www.luogu.com.cn/problem/P3386
参考ブログ:
https://23613.blog.luogu.org/solution-p3386
アルゴリズム:ハンガリーのアルゴリズムは本質的に貪欲です
ここでコードはあまり説明しません.二分図で使われているアルゴリズムを専門に説明するブログがあります.
https://blog.csdn.net/aiwo1376301646/article/details/104234482
 

#include 

using namespace std;
const int maxn=1e3+1;
bool f[maxn][maxn],used[maxn];
int match[maxn],n,m,e,x,y;

bool dfs(int pos)
{
    for(int i=1;i<=m;i++)
    {
        if(f[pos][i]&&!used[i])
        {
            used[i]=true;
            if(!match[i]||dfs(match[i]))
            {
                match[i]=pos;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;i++)
    {
        scanf("%d%d",&x,&y);
        if(x<=n&&y<=m)f[x][y]=true;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(used,false,sizeof(used));
        if(dfs(i))ans++;
    }
    printf("%d
",ans);
    return 0;
}