这数据范围是真的吗

P3376 【模板】网络最大流

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

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

by Niko！ @ 2020-06-15 21:34:15

@Flying_Bird 什么意思，复杂度不对就是不对，和考察点有什么关系

by ziiidan @ 2020-06-15 21:37:52

知乎上好像有把复杂度卡满的办法，不知道对不对，可以去看一下，至于实际应用，应该不会有人搞出来那么奇怪的建模

by Kubic @ 2020-06-15 21:38:28

~~网络瘤由于太毒瘤了，所以没几道复杂度正确的~~

by Niko！ @ 2020-06-15 21:39:37

@Kubic https://codeforces.ml/problemset?tags=flows 这里面应该没有假的吧

by FZzzz @ 2020-06-15 21:40:18

@Kubic 不会吧，一般出题人不都是把复杂度放低到 dinic 稳稳能过而通过建图来卡 EK 嘛/fad

by Kubic @ 2020-06-15 21:40:57

大概是的，CF数据范围比较真实

~~不像国内毒瘤出题人~~

by Polaris_Dane @ 2020-06-15 21:40:59

反正尽量出不会导致误解的数据范围比较好

by Kubic @ 2020-06-15 21:42:03

~~出题人也知道自己数据是用脚造的，所以只好扩大数据范围了~~

by FZzzz @ 2020-06-15 21:42:04

所以还是应该把复杂度放低到 dinic 能接受？然后 EK 卡一下比较好

by Niko！ @ 2020-06-15 21:43:05

有没有管理能处理一下 @一扶苏一 @皎月半洒花