为什么Dinic这么优化就能快??
查看原帖
为什么Dinic这么优化就能快??
476709
Himeno_Sena楼主2022/2/12 13:50
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]){
2022/2/12 13:50
加载中...