这数据范围是真的吗

P3376 【模板】网络最大流

Niko！ @ 2020-06-15 21:25:03

如果我没记错 Dinic 复杂度不是 O(V^2E) 吗，V = 10^4, E = 10^5 怎么回事

by UltiMadow @ 2020-06-15 21:26:10

跑不满

dinic过 1e5都有（

by xhQYm @ 2020-06-15 21:26:30

跑不满吧。。不过确实理论复杂度好像过不去

by Niko！ @ 2020-06-15 21:26:55

@UltiMadow 不能因为对非构造数据跑不满就出这样的数据范围吧，随机数据暴力 LCA 还跑不满呢

by Smile_Cindy @ 2020-06-15 21:27:01

@Niko！理论复杂度确实过不去，详见最大流加强版：预流推进

by hly1204 @ 2020-06-15 21:27:20

@Niko！这个题EK我之前也过了，可能是管理考虑模板题的原因没有加强？

by Smile_Cindy @ 2020-06-15 21:27:21

@Niko！ https://www.luogu.com.cn/problem/P4722

by Smile_Cindy @ 2020-06-15 21:27:50

@hly1204 根据相关法律法规，网络流的题目不卡Dinic/ISAP但可以卡EK

by UltiMadow @ 2020-06-15 21:28:34

@Niko！但是卡满dinic很难，特别是加了当前弧之后（

所以出题人基本不会卡你

然后一般考试的网络流题的数据范围不会这么大

by Semsue @ 2020-06-15 21:28:37

网络流卡Dinic/ISAP就是丧心病狂了

by Niko！ @ 2020-06-15 21:28:40

哪有相关法律法规

| 下一页