数据结构篇（二分图）最大匹配模板_数据结构最大匹配数是什么意思-CSDN博客

本文链接：https://blog.csdn.net/keepcoral/article/details/79810552

本文通过一个具体的实例介绍了如何使用匈牙利算法解决二分图的最大匹配问题。具体地，针对给定的男女队员匹配关系，算法通过深度优先搜索的方式寻找最优匹配方案，最终输出最大匹配对的数量。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：给了n个男队员，m个女队员，并且给了k个匹配关系（男女匹配），那么最大可以匹配出多少队（一男一女）？

二分图的基本应用，求的是最大匹配数，用的是匈牙利算法，但我基本没看明白，只能照着模板码一遍了

有机会以后再补

5 4 14
1 1
1 2
2 3
3 2
4 2
4 3
4 4
5 4
5 2
5 3
3 3
2 4
1 3
2 1     输出   4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
using namespace std;
int map[1000][1000];
int vis[1000];
int link[1000];
int n,m;
int dfs(int a)
{
    int i;
    for(i=1; i<=m; i++) //遍历女队员
    {
        if(map[a][i]&&!vis[i])//vis用来标记女队员是否被遍历过
        {
            vis[i]=1;
            if(link[i]==0||dfs(link[i]))//如果没有匹配则直接匹配
            {
                link[i]=a;
                return 1;
            }
            //如果已经匹配则，递归看是否能够修改
        }
    }
    return 0;//这个男队员直接匹配失败
}
int main()
{
    int i,a,b,k;
    int ans=0;

        scanf("%d%d%d",&n,&m,&k);
        ans=0;
        for(i=1; i<=k; i++)
        {
            scanf("%d%d",&a,&b);
            map[a][b]=1;
        }
        for(i=1; i<=n; i++) //遍历男队员
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ans++;
           // for(int j=1;j<=n;j++) printf("%d ",link[j]);
            //printf("\n");
        }
        printf("%d\n",ans);

}
/*
5 4 14
1 1
1 2
2 3
3 2
4 2
4 3
4 4
5 4
5 2
5 3
3 3
2 4
1 3
2 1
*/