首先  摆出概念

二分图

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

如图  就是顶点能分成两部分 且两部分内的顶点互相不连的图  就是二分图

匹配

在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点

最大匹配

一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

比如 图一的两条红线就是一个匹配  图二也是一个匹配 并且 图二是最大匹配

            图一                       图二

匈牙利算法

匈牙利算法用来求二分图的最大匹配数

原理解析  建议搭配食用：https://blog.csdn.net/holly_Z_P_F/article/details/89043041

简述以下这个算法的思路

两个顶点集合 A {a1,a2,a3,a4....}     B{b1,b2,b3,b4.......}

我们给顶点B集中的点做匹配  枚举B中顶点 每个都作如下操作

搜索 和 b1 有连线且没搜索过的点   假设是a1

        如果 a1还没做匹配（link[a1]==0） 那就 link[a1]=b1  代表和b1连上了

        如果a1已经和b2做了匹配了  那就b2能不能换个匹配的 能换就换 让a1和b1连 不能换 那b1再试试别的

借助题目看下

模板题51nod2006

代码+注释

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
using namespace std;
int x,y,n,m,cnt;
int e[110][110];
int v[10000];
int link[10000];
bool find(int x){
    for(int i=1;i<=n-m;i++){//遍历B集合
        if(e[x][i]&&!v[i]){//有连线且未标记
            v[i]=1;/标记
            //B中的这个点还没匹配或者已经匹配了但是所匹配的点还能换
            if(link[i]==0||find(link[i])){
                link[i]=x;return true;//匹配上
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d",&m,&n);
    while(scanf("%d%d",&x,&y)&&x!=-1&&y!=-1){
        e[x][y-m]=1;//代表连线
    }
    for(int i=1;i<=m;i++){//枚举A集合
        memset(v,0,sizeof(v));
        if(find(i))cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}