二分图匹配的匈牙利算法

二分图最大匹配

    二分图最大匹配的经典匈牙利算法是由Edmonds在1965年提出的，算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。
匈牙利算法的本质实际上和基于增广路特性的最大流算法还是相似的，只需要注意两点：
（一）每个X节点都最多做一次增广路的起点；
（二）如果一个Y节点已经匹配了，那么增广路到这儿的时候唯一的路径是走到Y节点的匹配点（可以回忆最大流算法中的后向边，这个时候后向边是可以增流的）。
    找增广路的时候既可以采用dfs也可以采用bfs，两者都可以保证O(nm)的复杂度，因为每找一条增广路的复杂度是O(m)，而最多增广n次，dfs在实际实现中更加简短。
算法思想： 

算 法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是 说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被 选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进 行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再 找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.
DFS:

 1 int w[NX][NY]; //X中的点到Y中的点的连接矩阵,w[i][j]是边的权
 2 int m[NY]; //Vyi的匹配对象
 3 int v[NY]; //在一次DFS中，Vyi是否被访问过
 4 bool dfs(int k){ //以Vxk为起点找交替路径
 5     int i;
 6     for(i=1;i<=N;i++){
 7         if(!v[i] && w[k][i]){ //如果Vyi未访问过，而且Vxk,Vyi有边连接
 8             v[i]=1;
 9             if(!m[i] || dfs(m[i])){ //如果Vyi是未浸润点，或者以Vyi原来的匹配点为起始，有扩张路径
10                 m[i]=k;
11                 return true; //扩张成功
12             }
13         }
14     }
15     return false;
16 }