如果m和n不相同时，最好把小的放上面，因为每次都是找上面一点的匹配点，找到满意的才会退出。若求最大权匹配，则匹配的点可以不存在（此时权值为0）。但如果求最小权匹配的话，直接把匹配的关系的权值取反的话，不存在的关系权值为0反而是最大的，所以就会出错。这时有两个解决方法，第一个就是保证上面的点会比下面的少，第二个就是关系的权值不直接取反，而是用一个大数减。。。
最大权匹配KM算法很早以前就学了，今天复习一下模板，发现它的思想我都不太清楚了。。现写下来，总结一下，加深印象。。。
该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为lx[ i ]，顶点Yj的顶标为ly[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，lx[ i ]+ly[j]>=w[i,j]始终成立。 首先KM算法的正确性是依据一个定理：若由二分图中所有满足lx[ i ]+ly[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。很显然这个定理我是证明不来的了，只能直接拿来用了。
如果先把lx[i]初始化为以i为端点的边权的最大值，ly[i]初值为0。那么对任意边都会满足lx[i]+ly[j]>=w[i,j]。首先如果有满足lx[i]+ly[j]=w[i,j]的点对，那么它们匹配，匹配完那些点又怎么办呢？
我们如果能找到一种办法，使得我们已经匹配的点仍满足lx[i]+ly[j]=w[i,j],并且使得没有扩展的点还有满足那等式的情况就好了。。。如果已经匹配过的点lx[i]-某个数d,ly[j]+d,满足上面的嘛？分四种情况(i,j是否已匹配好)讨论：
（1）如果i,j正好匹配好，那么一加一减，还是匹配好的
（2）如果i,j都没匹配，那么lx[i]和ly[j]根本就没变
（3）如果i匹配好了，j没匹配，那么lx[i]小了，ly[j]没变，所以lx[i]+ly[j]减小就可能等于w[i,j]了
（4）如果i没匹配，j匹配好了，那么和增大，不会多匹配。
上面四种情况讨论完后，就可看出上面的改变可能使的匹配更大权。至于d怎么确定，d应该尽量大，但同时不能一下多了两个匹配，所以是没匹配的i,j中lx[i]+ly[j]-w[i,j]最小值。这里有个优化，每次找最小值要O(n^2)，但用个slack数组只要O(n)了。模板如下：