hly1204的博客

博客

Dinic 和 Hopcroft-Karp 算法效率差距有 10 多倍正常吗？

2021-10-30 23:13:07 By hly1204

https://judge.yosupo.jp/submissions?problem=bipartitematching&user=&status=AC&lang=&order=-id&page=0&pageSize=100 这个题的提交记录里用 Hopcroft-Karp 算法的可能在 150ms 上下，但是 Dinic 的在 2 到 4s 上下，我自己写的好像接近 5s 保守算 2s 的话，效率差距也有 10 多倍，这是为什么？是常数差距本来就那么大还是别的原因？完全不懂，求解！

二分图

skip2004

一个是 $\sqrt(n)$ 次对 $200000$ 个点 $300000$ 条双向边的图 BFS DFS，一个是 $\sqrt(n)$ 次跑 bfs 和一些数组访问，但 bfs 接近于 $100000$ 个点 $100000$ 条单向边，形式也比 dinic 的 bfs 简单，我觉得差距很大也挺正常。

2021-10-31 15:18:28
回复

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。