Marriage Problem <二分图最大权匹配>

在一个小镇上。有8男8女要相亲。B1,B2,B3,B4,B5,B6,B7,B8 和 G1,G2,G3,G4,G5,G6,G7,G8  他们都已经相互了解过了。并且对对方有一个满意指数（0-99） （一般会有一张表格给出）

现在要求怎么让他们配对使得所有情侣的满意度之和最大。

解法： 这是一个二分图最大权匹配问题。

我们可以把所有男生放在一个集合B里面，所有女生放在集合G里。

满意度可以看作是集合B中的元素连上G中元素的边上的权重。

要求的就是权重和最大。

对于这个问题，我们有KM算法来进行求解

KM算法：求的是完备匹配下的最大权匹配。

key word：

完备匹配：X点集中的所有点都能匹配到一个Y点集中的点，同样在Y点集中所有点都能匹配到X点集中的一个点。

相等子图：二分图中所有满足A[i]＋B[j] ＝ w[i,j]的边构成的子图。

增广路径（argument path），增广路径有以下特性：

     1. 有奇数条边

     2. 起点在二分图的X边，终点在二分图的Y边

     3. 路径上的点一定是一个在X边，一个在Y边，交错出现。

     4. 整条路径上没有重复的点

     5. 起点和终点都是目前还没有配对的点，其他的点都已经出现在匹配子图中

     6. 路径上的所有第奇数条边都是目前还没有进入目前的匹配子图的边，而所有第偶数条边都已经进入目前的匹配子图。奇数边比偶数边多一条边

         7. 于是当我们把所有第奇数条边都加到匹配子图并把条偶数条边都删除，匹配数增加了1.

重难点： 寻找增广路径

寻找增广路径的办法：增广路径有两种寻径方法，一个是深搜，一个是宽搜。例如从x2出发寻找增广路径，如果是深搜，x2找到y0匹配，但发现y0已经被x1匹配了，于是就深入到x1，去为x1找新的匹配节点，结果发现x1没有其他的匹配节点，于是匹配失败，x2接着找y1，发现y1可以匹配，于是就找到了新的增广路径。如果是宽搜，x1找到y0节点的时候，由于不能马上得到一个合法的匹配，于是将它做为候选项放入队列中，并接着找y1，由于y1已经匹配，于是匹配成功返回了。相对来说，深搜要容易理解些，其栈可以由递归过程来维护，而宽搜则需要自己维护一个队列，并对一路过来的路线自己做标记，实现起来比较麻烦。

解题步骤：

1.二分图最大权值问题可转化为：寻找有完备匹配的相等子图，也就是构建一个权重和最大的二分子图。

2.初始化： 一开始先让X的定标设为对应到Y集合里面的最大值 A[i] = w[i,j]  且 B[j] = 0

3.看这样的定标能否完备匹配,如果不能则找增广路径，得到两个集合S和T

4.根据所得集合S，T 可以求出d

5 S里面的元素定标减去d，T里面的元素定标加上d

6，再次看是否完备匹配，如果没有 重复上面过程