关于 hack 卡掉了 ISAP 但不卡 dinic
查看原帖
关于 hack 卡掉了 ISAP 但不卡 dinic
765446
MichaelWong楼主2023/6/23 10:01

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

想知道为什么这个图里 ISAP 会这么慢?为什么 dinic 就没有被卡?不是很理解 ISAP 和 dinic 复杂度分布的区别。

2023/6/23 10:01
加载中...