用简单易懂或图形的方式解释一下匈牙利算法

Question

http://zh.wikipedia.org/wiki/匈牙利算法

维基百科里的不容易看懂

Answer 1

匈牙利算法就是分别从二分图的左侧每一个点开始找到一条增广路径，且每找到一条增广路径P，则与匹配M进行异或运算，令 M = M xor P。最终得到 M 为最大匹配。
代码实现，稍后补充。
图片说明如下：

Answer 2

推荐 byvoid 前辈的一篇文章：http://www.byvoid.com/blog/hungary

刚才我翻出了一篇我写的旧文，或许对你有帮助（不严谨的地方恳请指出）
c++ bool crosspath(long k) { for (long i=1;i<=adjl[k][0];i++) { long j=adjl[k][i]; if (!used[j]) { used[j]=true; if (mat[j]==0 || crosspath(mat[j])) { mat[j]=k; return true; } } } return false; }

这是核心代码，功能是判断是否存在从k出发的一条增广路径（调用该函数前，used被清为false）。

首先明确，点k是在左侧而j在右侧。mat[j]表示的，则是右侧的j点“被”左侧的k点匹配。

那么，不妨尝试一下这样的拟人的方式：
mat[j]表示j的另一半，而used[j]表示j是否现在在约会。这两者间没有直接联系（在hungary函数中，调用crosspath之前要清空used而不能清空mat）。
调用crosspath(k)， 就是一个匈牙利人告诉k： 你赶紧去找个对象！

然后k列了一串“异性”名单（邻接表）， 挨个的叫出来约会。

k对j说： 我喜欢你，咱们处吧
j有两种情况 ：
1. 欣然应允（反正我现在孤身一人）
2. 已经有了mat[j], 不想抛下他，让他孤零零的

k : 那我帮mat[j] 再找一个好了
j: 你要是能帮他找到一个新的，我就跟你走 -.-
k : crosspath( mat[j] )

当然了，k正在约j，要是在j答应自己前，就被别人领走了，不就乱了吗。所以，要用used[j]标记一下。如果最后成了，那就去登记领证 mat[j] = k，然后告诉哥们，庆祝一下 return true

如果没处成，为什么不清除标记呢？因为，任何一个人要约j， 都要去帮mat[j] 找新对象。自己没完成这项伟业，间接的通过别人，也必然做不到。所以，如果下次再卡到j上，那就及早死心，换下一个人了。

解释完了crosspath的过程，hungary的过程就很容易理解了：让左侧的每一个人去轮流去找对象。因为每次crosspath返回true的时候，都意味着右侧有一个人告别单身，所以，就可以将匹配数+1. 如果某一次匹配是不恰当的，那么，肯定会在接下来有人横刀夺爱。所以，可以获得最优解（此处没有给出严格证明）