在一个小镇上。有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...
Comments
Post a Comment