分别用 dinic 和 ISAP 跑,dinic 非常快地过了,但是 ISAP 却在最后一个 hack 数据的时候非常慢,时长大概在 8.70s 左右,输出发现在day=124,226,328,431,533,635,738,840. 时跑得极慢,使用 clock() 函数输出时间可以发现,dinic 单次求最大流的时间始终不超过 1ms, 而同样的图 ISAP 的单次求最大流时间一直在随 day 波动递增,大约在 day>50 后开始时间在 1ms 左右,在 day>200 后时间来到了惊人的 10ms, 感觉好像就是纯粹的在这个图里面 ISAP 败给 dinic 了。
想知道为什么这个图里 ISAP 会这么慢?为什么 dinic 就没有被卡?不是很理解 ISAP 和 dinic 复杂度分布的区别。