为什么当前弧优化这样会很慢?

P3376 【模板】网络最大流

StarPatrick @ 2023-05-03 20:26:52

for (int p=cur[i];p<v[i].size();p++) {
    cur[i] = p;
    if (v[i][p].u&&dis[v[i][p].i]==dis[i]+1) {
        ll flow = dfs(v[i][p].i, min(u, v[i][p].u));
        u-=flow, all+=flow;
        v[i][p].u-=flow;
        v[v[i][p].i][v[i][p].back].u+=flow;
        if (!u) return all;
    }
}

这个59ms

for (int p=cur[i];p<v[i].size();p++) {
    cur[i] = p+1;
    if (v[i][p].u&&dis[v[i][p].i]==dis[i]+1) {
        ll flow = dfs(v[i][p].i, min(u, v[i][p].u));
        u-=flow, all+=flow;
        v[i][p].u-=flow;
        v[v[i][p].i][v[i][p].back].u+=flow;
        if (!u) return all;
    }
}

这个659ms,仅仅改了这一个地方

cur[i] = p+1;

理应说来应该更快啊,为啥慢了好多?


by reveal @ 2023-05-03 20:30:47

@cqbzzqw 因为当前边并不一定是断开的,可能推过来的流用完了导致退出了,但是此时当前边仍可以推流。

考虑后面为什么要写 if (!u) return all; 就是为了不会错误的跳边,不然这一句为什么不写循环条件里。


by Miraik @ 2023-05-03 20:33:12

@cqbzzqw 你这条边这次也不一定流满,那你这一轮不再访问它就会导致轮数增加


by TulipeNoire @ 2023-05-03 20:36:55

对的,我也是这样的,十分疑惑。


by Others @ 2023-05-03 20:44:40

@cqbzzqw 1~n-2 与 n-1 连边,流量1,n-1与n连边流量n-2,这样你每 dfs 到 n-1 一次,只用了一个流量,就会退回去(cur 超过了 size),然后搞一遍分层。

你说挂不挂。


by Others @ 2023-05-03 20:45:33

哦,还得有个 0 给 1~n-2 流量。


by StarPatrick @ 2023-05-03 21:00:42

@DitaMirika @reveal @Others 悟了,谢谢大佬们


|