关于HK算法的一点疑问
  • 板块学术版
  • 楼主happybob
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/19 21:20
  • 上次更新2024/3/20 08:06:28
查看原帖
关于HK算法的一点疑问
332914
happybob楼主2024/3/19 21:20

二分图匹配的 HK 算法,每次是找一个极大最短增广路集合,每条增广路长度一样,且都等于目前匹配的最短增广路长度。那么在 BFS 之后的 DFS 分层时,应该只遍历到最靠左的有增广路的层内。

但是我第一次写的时候,并没有保证这个,也就是说我没有保证他是最短的,但是找到的是一个极大互不相交增广路集,并进行增广。这个做法复杂度有保证吗?似乎比我改后跑的更快。

2024/3/19 21:20
加载中...