KM算法的最小权值婚配、完备匹配详细易懂总结-结合例题
首先，有如下问题：
1.针对于完全匹配G＝<V1，V2，E>，我们规定用V1去匹配V2的点,那么完备匹配定义为对于V1的所有点都有与之对应的V2的点匹配，那么如果对于V1对应于V2的点的匹配有的关系关系不确定的时候怎么呢？
2.通过KM求得最大权值匹配..如果要求最小权值匹配，那么怎么办呢？
这里给出总结，对自己刚接触KM的记录：
对于1.：
引用：如果图中|V1|！=|V2|，理解的时候可以补充一些虚拟的点，让两边的点数相等（完备匹配就成为完美匹配了）。当然虚拟点的边之都是0。
那么在匹配的过程中，对于虚拟点的边为0，那么求出完备匹配之后的权值就是答案..因为如果是没有的边匹配了...但是我们的虚拟边是0，那么对于匹配的最优权值没有影响
那么还有的题目中V1对于V2的点的关系不确定...就如hdu2426.。。
题意：这里有N个学生，M个寝室，E个意愿，每个意愿占一行，包括S，R，V表示S学生对R房间的渴望为V，那么这里的V如果为0表示这个学生对R房间表示中立，不喜欢也不讨厌，如果V为负数，就是不喜欢，不能安排，而且这里如果没有列出S对R的意愿，那么就表示不愿意，那么问题是根据给出的数据，输出安排学生的最大意愿是多少，如果不能安排就输出-1,
那么这里很明确是用学生匹配寝室，但是题意要求如果没有给出某学生对某寝室的关系，那么就是表示这个学生不喜欢这个寝室，那么我们就可以这样处理，初始有一个map[i][j]表示i学生对j 寝室的关系，我们初始全部为-1，然后去匹配，对于匹配过程中为负数的我们就不考虑，那么就能根据是否完备匹配输出答案(此题我另有详细解题报告)
对于2：
我们可以看hdu2255这个KM完备最大权值匹配的裸题.....如果把题意改为在N*N中的值为不满意度(数值越大表示越不满意)，那么为了让所有的人不满意度最低，我们怎么安排对应的房子呢？
那么对于N*N的值我们全部取负数存于map[i][j]中，然后我们在通过KM算法去求解，那么我们会发现对于可行顶标的 lx[MAX] 初始选择最大的值(此时全部是负数)实际上就是正数(也就是不满意度)的最小值，那么通过KM求解出来的最大匹配总和的时候实际就是不满意度的最小值， 那么这里给出几个我最近接触的KM最小权值匹配题目 hdu3488回路旅游、hdu1853回路旅游(和之前的题有点不同)、hdu1533回家（都会对应在近期给出详细解题报告）
个人愚昧观点，欢迎指正与讨论