KM算法 用于求二分图的最佳完美匹配 即权值最大的完美匹配
如果你也是个刚来学习KM算法的人 大概的用途肯定还是知道的吧 还是直接说重点吧
首先 理解KM算法前 必须有以下3个概念
1.可行顶标 对于一个赋值二分图G(x,y,e,w) (x,y 代表二分图的两边顶点标号 e代表边 w代表边的权值 ) 我们对两边的每一个顶点都赋予一个额外的值 使得对于二分图G内的所有边 e=xy 均有 lx(x)+ly(y)>=w(xy)
其实不管什么样的图 什么样的边权 可行顶标必然存在 例如 lx(x)=max w(xy) ly(y)=0
2.在已经赋值可行顶标的二分图中 保留所有lx(x)+ly(y)=w(x)(y) 的边 删去其他的边 形成的新的图称为生成子图
3.在生成子图中的任意一个完美匹配都是最佳完美匹配 反过来 G的任意一个最佳完美匹配都包含在 生成子图中
可能第三条定理来的有些突然 有点让人懵逼 但是你只要稍微想一下 你就会发现这很明显
因为这个匹配 他所有权值之和就是可行顶标之和 而 可行顶标之和必然是权值之和最大的（因为第一条
但问题是 对于当前顶标所推出的生成子图 并不一定存在完美匹配 这时，可以用某种方法对顶标进行调整。调整的方法是：根据最后一次不成功的寻找交错路的DFS，取所有i被访问到而j没被访问到的边(i,j)的lx[i]+ly[j]-w[i][j]的最小值d。将交错树中的所有左端点的顶标减小d，右端点的顶标增加d。经过这样的调整以后：原本在导出子图里面的边，两边的顶标都变了，不等式的等号仍然成立，仍然在导出子图里面；原本不在导出子图里面的边，它的左端点的顶标减小了，右端点的顶标没有变，而且由于d的定义，不等式仍然成立，所以他就可能进入了导出子图里。
如果还看不懂 我只能贴上我学习过程看的博客了 毕竟只有文字可能不好理解 我又懒
上面的文字理解来源
萌萌哒的妹子写的图文详解
最后是来几套题