令G = （X,*,Y）是一个二分图，其中，X = {x1,x2,...xm}, Y = {y1,y2,...yn}。令M为G中的任一个匹配。 1）讲X的所有不与M的边关联的顶点标上（@），并称所有的顶点为未被扫描的。转到 2）。 2）如果在上一步没有新的标记加到X的顶点上，则停止。否则转到 3）。 3）当存在X被标记但未被扫描的顶点时，选择一个被标记但未被扫描的X的顶点，比如，xi,用(xi)标记Y的所有顶点，这些顶点被不属于M且尚未标记的边连到xi .现在，顶点xi是被扫描的。如果不存在被标记但未被扫描的顶点，则转到 4）。 4）如果在步骤 3）没有新的标记被标到Y的顶点上，则停止。否则，转到 5）。 5）当存在Y被标记但未被扫描的顶点时，选择Y的一个被标记但未被扫描的顶点，比如yi，用(yi)标记X的顶点，这些顶点被属于M且尚未标记的边连到yi.现在，顶点yi是被扫描的。如果不存在被标记但未被扫描的顶点，则转到 2）。 也可以叙述为： [ZZ]匈牙利算法 关键在于匈牙利算法的递归过程中有很多重复计算的节点，而且这种重复无法避免，他不能向动态规划一样找到一个“序”将递归改为递推。
算法中的几个术语说明： 1。二部图： 如果图G=(V,E)的顶点集何V可分为两个集合X,Y，且满足 X∪Y = V, X∩Y=Φ，则G称为二部图；图G的边集用E(G)表示，点集用V(G)表示。2。匹配： 设M是E(G)的一个子集，如果M中任意两条边在G中均不邻接，则称M是G的一个匹配。M中的—条边的两个端点叫做在M是配对的。 3。饱和与非饱和： 若匹配M的某条边与顶点v关联，则称M饱和顶点v，并且称v是M-饱和的，否则称v是M-不饱和的。 4。交互道： 若M是二分图G＝(V,E)的一个匹配。设从图G中的一个顶点到另一个顶点存在一条道路，这条道路是由属于M的边和不属于M的边交替出现组成的，则称这条道路为交互道。 5。可增广道路： 若一交互道的两端点为关于M非饱和顶点时，则称这条交互道是可增广道路。显然，一条边的两端点非饱和，则这条边也是可增广道路。 6。最大匹配： 如果M是一匹配，而不存在其它匹配M'，使得|M'|>|M|，则称M是最大匹配。其中|M|表示匹配M的边数。 7。对称差： A，B是两个集合，定义 A⊕B = (A∪B)\(A∩B) 则A⊕B称为A和B的对称差。 定理：M为G的最大匹配的充要条件是G中不存在可增广道路。 Hall定理：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于 X的任意一个子集A，和A邻接的点集为T(A)，恒有： |T(A)| >= |A|
匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为： 1。任给初始匹配M； 2。若X已饱和则结束，否则进行第3步； 3。在X中找到一个非饱和顶点x0，作 V1 ← {x0}, V2 ← Φ 4。若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2； 5。若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M⊕E(P)，转2； 6。由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4；
模板 对应HDU2063
代码 #include < stdio.h > #include < string .h > const int N = 502 ; int map[N][N]; int link[N],useif[N]; int n,m; int can( int t){ for ( int i = 1 ;i <= m;i ++ ) { if (useif[i] == 0 && map[t][i]) { useif[i] = 1 ; if (link[i] ==- 1 || can(link[i])) { link[i] = t; return 1 ; } } } return 0 ;} int maxmatch(){ int i,num; num = 0 ; memset(link, - 1 , sizeof (link)); for (i = 1 ;i <= n;i ++ ) { memset(useif, 0 , sizeof (useif)); if (can(i)) num ++ ; } return num;} int main(){ int k,a,b; while (scanf( " %d " , & k),k) { scanf( " %d%d " , & n, & m); memset(map, 0 , sizeof (map)); while (k -- ) { scanf( " %d%d " , & a, & b); map[a][b] = 1 ; } printf( " %d\n " ,maxmatch()); } return 0 ;}
HDOJ_1068 (二分图最大独立集=n-m/2) HDOJ_1150 (二分图最小顶点覆盖=m) HDOJ_1151 (二分图最小路径覆盖=n-m) HDOJ_1281(求完美匹配 的个数) HDOJ_1498(最大匹配m=遍历每个点需要的次数) 在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是二分图的“最小顶点覆盖”。 用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。 节点数（n），最大匹配数（m）。
转载于:https://www.cnblogs.com/DreamUp/archive/2010/08/18/1802039.html
相关资源：二分图完备匹配(匈牙利算法)