警示后人,Dijkstra 费用流(Primal-Dual 原始对偶)如何卡常
查看原帖
警示后人,Dijkstra 费用流(Primal-Dual 原始对偶)如何卡常
105050
myee楼主2023/7/23 13:24

时限只开 1s\rm1s 导致 Dijkstra 费用流惨遭卡常。。。

  1. Dijkstra 费用流写 EK,别写 Dinic;Dinic 的 dfs 常数太大了,而且实际上数据基本卡满了增广轮数。
  2. 在找最近点时,用一个双向链表维护当前还没有被访问过的点集,由于访问的点少了,内存访问也比较连续,所以很快。
  3. 在枚举出边时,只枚举有边的部分。
2023/7/23 13:24
加载中...