图4-15

已经无法添加新的增广路径了，算法结束。男女双方达到最大配对，红色标记最大配对边:{Al--->Beatrice，Bob--->Danielle，Christ--->Alice, Dan--->Carol}。

匈牙利算法的核心是：不断寻找增广路，并扩展增广路。不断重复这一过程直到找不到增广路为止。如图4-16所示。

图4-16

具体步骤：

1. 首先从左边第一个点出发，寻找增广路黑色标记 1->2(没错，这个也是增广路)，然后翻转关系变为红色标记1->2。
2. 从左边第二个点出发，寻找增广路3->2->1->4,然后翻转关系变为红色标记3->2->1->4。
3. 从左边第三个点出发，寻找增广路5->4->1->2->3->6,然后翻转关系5->4->1->2->3->6。
4. 至此，我们已经找到二分图G的最大匹配数，同时这个也是完全匹配。

题目描述
小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 N×N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：
行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）
列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）
游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小Q决定写一个程序来判断这些关卡是否有解。

解：

解题思路：我们把矩阵转化为二分图（左侧集合代表各行，右侧集合代表各列，某位置为1则该行和该列之间有边）。我们想进行一系列交换操作，使得X1连上Y1，X2连上Y2，……

假设N=4, 建立4×4的01矩阵。如图5-1所示。

图5-1

原问题变为将矩阵转化为二分图，求最大匹配。

图5-2

如图5-2所示，采用匈牙利算法，红色标记最大匹配为｛X1--->Y4, X2--->Y2, X3--->Y1, X4--->Y3｝。

结果矩阵为(如图5-3所示)：