匈牙利算法本质就是一个个的匹配，对于当前的处理的对象i,假设他的匹配对象为j,但是j已经和v匹配好了，那么就让v去找找着能不能和别人匹配

v可以和别人匹配则i与j匹配，不能则i去找别人匹配

另外引入几个定义和结论：

1:最大匹配数 + 最大独立集 = n + m（n,m为二分图两边的节点数）

2:二分图的最小顶点覆盖数 = 最大匹配数

3:最小路径覆盖 = 最大独立集

最大独立集是指：求一个二分图中最大的一个点集，该点集内的点互不相连。

最小顶点覆盖是指： 在二分图中，用最少的点，让所有的边至少和一个点有关联。

最小路径覆盖是指：

对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

 

最大匹配是指：

对于二分图的所有边，寻找一个子集，这个子集满足两个条件，

1：任意两条边都不依赖于同一个点。

2：让这个子集里的边在满足条件一的情况下尽量多。

 算法的证明如下：http://blog.csdn.net/yuxue_23/article/details/12224067

然后是模版:

bool find(int x){    int i,j;    for (j=1;j<=m;j++){    //扫描每个妹子        if (line[x][j]==true && used[j]==false)              //如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了）        {            used[j]=1;            if (girl[j]==0 || find(girl[j])) {                 //名花无主或者能腾出个位置来，这里使用递归                girl[j]=x;                return true;            }        }    }    return false;}int main(){for (i=1;i<=n;i++){    memset(used,0,sizeof(used));    //这个在每一步中清空    if find(i) all+=1;}  return 0;       }

然后是本题代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include