KM算法总结

km算法我的理解

 

刷了不到20道题。。。回来总结一发。。

如果题目求的是最小权值匹配,比较好的做法是将权值取取值,最后res再取负就好。需要注意的是初始化的时候w和lx要比所有值都小,所以要ms(lx,0xc0)

最正确解最小权匹配的办法是用一个很大的数-当前边权值,而不是直接对边权取反(这样只能处理左右点相等的完全二分图,即K(n, n)(bin神博客看到的)

有时候需要考虑无解的情况,一般如果有无解的情况,对应了存在lx[i]=初始化的值。

不少题目有一个点都是先用一种暴力或者不暴力的方法处理出w,然后裸的km  hdu3722解题报告

有向图的覆盖可以对应二分图最佳匹配的模型,用km算法搞 hdu1853解题报告

遇到了一种题是之前有一些已经安排好了,然后仍然求最优匹配,并且尽可能少得改变原有的安排。hdu2853解题报告 不得不说做法很厉害。

 

还有一些网络流的题似乎也可以转化成km来做,打算先去搞一发网络流再去A.

选区_077

这些题里就两个比较好,一个是对于有向环覆盖的,第一次遇到真想不到,还有一个就是那个权值×k的。。。佩服。。。

其他的都是套路。

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz