用匈牙利算法求二分图的最大匹配 什么是二分图，什么是二分图的最大匹配，这些定义我就不讲了，网上随便都找得到
二分图的最大匹配有两种求法，第 一种是最大流（我在此假设读者已有网络流的知识）；第二种就是我现在要讲的匈牙利算法
这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的 特点，把最大流算法做了简化，提高了效率
匈牙利算法其实很简单，但是网上搜不到什么说得清楚的文章
所以我决定要写一下
最大流算法的核心问题就是找增广路径（augment path）
匈牙利算法也不例外，它的基本模式就是： 初始时最大匹配为空 w hile 找得到增广路径 do 把增广路径加入到最大匹配中去 可见和最大流算法是一样的
但是这里的增广路径就有它一定的特殊性，下面我来分析一下
（注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图
每条边也不需要有方向
） 图 1 图 2 图 1 是我给出的二分图中的一个匹配：［1，5］和［2，6］
图 2 就是在这个匹配的基础上找到的一条增广路径：3->6->2->5->1->4
我们借由它来描述一下二分图中的增广路径的性质： (1)有奇数条边
(2)起点在二分图的左半边，终点在右半边
(3)路径上的点一定是一个在左半边，一个在右半边，交替出现
（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦
） (4)整条路径上没有重复的点
(5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的
（如图 1、图 2 所示，［1，5］和［2，6］在图 1 中是两对已经配好对的点；而起点 3 和终点 4 目前还没有与其它点配对
） (6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中
（如图 1、图 2 所示，原有的匹配是［1，5］和［2
