继续开坑~btw,I love bx2k.
这次来讲HK算法。我二分图最大匹配只会HK是不是药丸QwQ
和所有匹配算法一样，中心思想还是找增广路。但是找增广路之前，我们要把整个图分层。
说到分层，Dinic选手是不是想到了些什么我是isap选手，是的，就是按Dinic的方法分层。
首先把左边所有没有匹配的点全部加入队列，层数为0，再把这些点通过非匹配边连向的右边的点的层数标为1，但是不加入队列，而是对于右边这些层数为1的点，如果它们有匹配点，就把匹配点再加入队列，层数标为2，后面的以此类推。
看到这里是不是觉得和一般图最大匹配有点类似呢，‘只用把一类点加入队列’，这样做才能体现出‘走一条非匹配边走一条匹配边’的增广路。
于是和Dinic一样，分层结束之后就可以找到每个点出发的最短的增广路，这也就是分层的意义。
接下来分类讨论，如果所有能搜到的右边点都有匹配点，那么不能再找到增广路了，算法结束。
否则，对于每个层数为0的左边点，找到他们连出去的最短的增广路，也就是每次走让层数加一的边的增广路。
可证明，一共只会执行O(sqrt(n))次上面的操作，于是总复杂度就是O(sqrt(n)$\times$(n+m))的。
然而用Dinic做也是这个复杂度，其实这个算法就是Dinic的二分图简化版？
这就是HK算法咯，是不是一个又好打又快的算法丫~还在犹豫什么，快去学吧！
其实具体细节和技巧依旧很复杂的大家就去看代码吧
另外欢迎大家来问我和二分/一般图最大匹配有关的问题
顺便说一句，我写的所有文章按Ctrl+A全选之后都会看到彩蛋
=w= 看到这句话的都是呆呆哒的神犇！ hhh
鄂公网安备 42010202000505 号