Dinic玄学复杂度没得讲
by sermoon @ 2018-02-09 07:48:18
isap都320ms呢
by iotang @ 2018-02-09 08:04:33
@[杜岱玮](/space/show?uid=64366)
然而Rank3的Dinic只跑了200ms（Rank1、2不为人知）
本蒟蒻（不知道弱到哪里去了）的ISAP跑了380ms
而模板题的ISAP稳居第一
比如由于分层图如果层次少的话那么就会提前结束bfs，而ISAP某些操作无法避免的重复做而不能比Dinic提前结束
by Creeper_LKF @ 2018-02-09 08:09:03
@[杜岱玮](/space/show?uid=64366)
dinic时间复杂度确实是$O(n^2m)$,最高标号预流推进时间复杂度是$O(n^3)$,但是dinic一般达不到上界，实际复杂度要好得多，最高标号预流推进卡上界卡的比较紧，就导致了最高标号预流推进要比dinic和ISAP在某些~~(大多数)~~时候比较慢.
by 单曦增 @ 2018-03-14 17:56:50