二分图匹配的 HK 算法,每次是找一个极大最短增广路集合,每条增广路长度一样,且都等于目前匹配的最短增广路长度。那么在 BFS 之后的 DFS 分层时,应该只遍历到最靠左的有增广路的层内。
但是我第一次写的时候,并没有保证这个,也就是说我没有保证他是最短的,但是找到的是一个极大互不相交增广路集,并进行增广。这个做法复杂度有保证吗?似乎比我改后跑的更快。