如果你Dinic TLE on #9

P3376 【模板】网络最大流

Jessica2333 @ 2023-09-03 16:19:22

如果是单路增广要用当前弧优化；多路增广在DFS的时候，如果这个点流不出去，要把它的dep记为0

by Twiter_ln @ 2023-11-03 11:44:32

@Jessica2333 多路增广：为什么要 dep[v]=0？

不是只会 dfs() 一次 bfs() 所构造的树形结构吗？

lli Dinic() {
    lli ans = 0;
    int cnt = 0;
    while(bfs()) ans += dfs(S, 0x3fffffffffffffff);
    return ans;
}

标记之后，第二次 dfs() 不就又标记回去了吗？

可以解释下吗，感谢 Thanks♪(･ω･)ﾉ

by Twiter_ln @ 2023-11-03 11:45:49

@Jessica2333 虽然我也 TLE #9。

by Twiter_ln @ 2023-11-03 19:52:04

@Twiter_ln Dbq，当我没说 /bz

|