Himeno_Sena @ 2022-02-12 13:50:15
ll dinic(ll x, ll flow){
if(x == t) return flow;
ll rest = flow, k, i;
for(i = now[x]; i && rest; i = nex[i]){
if(val[i] && d[to[i]] == d[x] + 1){
k = dinic(to[i], min(rest, val[i]));
if(k == 0) d[to[i]] = 0;
val[i] -= k;
val[i ^ 1] += k;
rest -= k;
if(rest == 0) break; //就是这句
}
}
now[x] = i;
return flow - rest;
}在循环开头的 i && rest 和上面那句的功能不是一样的么？
for(i = now[x]; i && rest; i = nex[i]){by Electro_Master @ 2022-02-12 14:00:38
@Himeno_Sena 这是老生常谈的问题了，if(rest == 0) break; 如果不加这句，会进入下一条边再跳出，有可能当前这条边没有流完，复杂度就会不对。
by BootsH @ 2022-02-12 14:05:43
@Electro_Master 借楼问一下，如果 for 写成
for (int& i = cur[u]; i && rest; i = g[i].next) 需不需要加那一句话
by Gao_yc @ 2022-02-12 14:08:06
@developer6hyx 一样需要（调dinic调了6h的巨大教训）
by Gao_yc @ 2022-02-12 14:09:07
P4177 不这样优化就会T
by Himeno_Sena @ 2022-02-12 14:15:31
@developer6hyx 我原先写的就是这样的
by Himeno_Sena @ 2022-02-12 14:21:10
@Electro_Master 为什么下一句跳出跳出复杂度就不对了，，不懂，，是因为 now[x] 记录变成下一条边了么？ 但是now[x]不就是记录下一条边的么。。
by BootsH @ 2022-02-12 14:23:43
@gao_yc ok，thx
by Electro_Master @ 2022-02-12 14:24:43
@Himeno_Sena now[x] 记录的是当前边，当前边流量没有用完，直接跳下一条就会导致 BFS 和 DFS 执行次数变多
by Himeno_Sena @ 2022-02-12 14:28:43
@Electro_Master 理解了，谢谢