前言：
高中时候老师讲这个就听得迷迷糊糊，有一晚花了通宵看KM的Pascal代码，大概知道过程了，后来老师说不是重点，所以忘的差不多了。

都知道二分图匹配是个难点，我这周花了些时间研究了一下这两个算法，总结一下
1.基本概念
M代表匹配集合
未盖点：不与任何一条属于M的边相连的点
交错轨：属于M的边与不属于M的边交替出现的轨（链）
可增广轨：两端点是未盖点的交错轨
判断M是最大匹配的标准：M中不存在可增广轨
2.最大匹配，匈牙利算法
时间复杂度：O(|V||E|)
原理：
寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。

修改M 为M&P。

即这条轨进行与M进行对称差分运算。

所谓对称差分运算，就是比如X和Y都是集合，X&Y=(X并Y)-(x交Y)
有一个定理是：M&P的边数是|M|+1，因此对称差分运算扩大了M
实现：
关于这个实现，有DFS和BFS两种方法。

先列出DFS的代码，带注释。

这段代码来自中山大学的教材
核心部分在dfs(x)，来寻找可增广轨。

如果找到的话，在Hungarian()中，最大匹配数加一。

这是用了刚才提到的定理。

大家可以想想初始状态是什么，又是如何变化的
view plaincopy to clipboardprint?
第二种方法BFS，来自我的学长cnhawk
核心步骤还是寻找可增广链，过程是：
1.从左的一个未匹配点开始，把所有她相连的点加入队列
2.如果在右边找到一个未匹配点，则找到可增广链
3.如果在右边找到的是一个匹配的点，则看它是从左边哪个点匹配而来的，将那个点出发的所有右边点加入队列
这么说还是不容易明白，看代码吧
view plaincopy to clipboardprint?
3.最佳匹配
加权图中，权值最大的最大匹配
KM算法：
概念：
f(v)是每个点的一个值，使得对任意u,v C V，f(u)+f(v)>=w[e u,v]集合H：一个边集，使得H中所有u,v满足f(u)+f(v)=w[e u,v]
等价子图：G f(V,H)，标有f函数的G图
理论：
对于f和G f，如果有一个理想匹配集合M p，则M p最优。

对于任意匹配集合M，weight(M)<weight(M p)
KM算法的实质是扩展G f，直到找到理想的匹配集合
伪代码
view plaincopy to clipboardprint?
最后给一个代码，跟伪代码的思路不是很一样。

从网上找的
view plaincopy to clipboardprint?。