为什么Dinic这么优化就能快??

P3376 【模板】网络最大流

@[Himeno_Sena](/user/476709) 这是老生常谈的问题了,`if(rest == 0) break; ` 如果不加这句,会进入下一条边再跳出,有可能当前这条边没有流完,复杂度就会不对。
by Electro_Master @ 2022-02-12 14:00:38


@[Electro_Master](/user/386569) 借楼问一下,如果 for 写成 ```cpp for (int& i = cur[u]; i && rest; i = g[i].next) ``` 需不需要加那一句话
by BootsH @ 2022-02-12 14:05:43


@[developer6hyx](/user/317805) 一样需要(调dinic调了6h的巨大教训)
by Gao_yc @ 2022-02-12 14:08:06


P4177 不这样优化就会T
by Gao_yc @ 2022-02-12 14:09:07


@[developer6hyx](/user/317805) 我原先写的就是这样的
by Himeno_Sena @ 2022-02-12 14:15:31


@[Electro_Master](/user/386569) 为什么下一句跳出跳出复杂度就不对了,,不懂,,是因为 now[x] 记录变成下一条边了么? 但是now[x]不就是记录下一条边的么。。
by Himeno_Sena @ 2022-02-12 14:21:10


@[gao_yc](/user/255581) ok,thx
by BootsH @ 2022-02-12 14:23:43


@[Himeno_Sena](/user/476709) `now[x]` 记录的是当前边,当前边流量没有用完,直接跳下一条就会导致 BFS 和 DFS 执行次数变多
by Electro_Master @ 2022-02-12 14:24:43


@[Electro_Master](/user/386569) 理解了,谢谢
by Himeno_Sena @ 2022-02-12 14:28:43


|