保存帖子
发现
索引
热门
陶片放逐
关于
警示后人,Dijkstra 费用流(Primal-Dual 原始对偶)如何卡常
板块
P6577 【模板】二分图最大权完美匹配
楼主
myee
当前回复
2
已保存回复
2
发布时间
2023/7/23 13:24
上次更新
2023/11/3 08:06:57
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
警示后人,Dijkstra 费用流(Primal-Dual 原始对偶)如何卡常
myee
楼主
2023/7/23 13:24
时限只开
1
s
\rm1s
1s
导致 Dijkstra 费用流惨遭卡常。。。
Dijkstra 费用流写 EK,别写 Dinic;Dinic 的 dfs 常数太大了,而且实际上数据基本卡满了增广轮数。
在找最近点时,用一个双向链表维护当前还没有被访问过的点集,由于访问的点少了,内存访问也比较连续,所以很快。
在枚举出边时,只枚举有边的部分。
2023/7/23 13:24
加载中...