关于Dinic的小问题

_Ts_ @ 2018-09-03 15:53:19

while(bfs()) while(int tmp = dfs(s, inf)) ans += tmp;

by SeKong @ 2018-09-03 16:01:08

本来就不需要while。。。

by 星小雨 @ 2018-09-03 16:25:16

并不需要。。这个是写的习惯来着？

by GKxx @ 2018-10-19 15:57:56

要看你的dfs里面是怎么写的

如果你的dfs是单路增广 外面就要这样写，如果里面是多路增广就不必了

如果dfs是这样写的：

int dfs(int x, int cf) {
    if (x == t || !cf) return cf;
    int getf = 0;
    for (int i = curr[x]; ~i; i = next[i], curr[x] = i)
        if (cap[i] > flow[i] && height[v[i]] == height[x] + 1) {
            int nf = dfs(v[i], min(cf, cap[i] - flow[i]));
            if (nf) {
                flow[i] += nf;
                flow[i ^ 1] -= nf;
                getf += nf;
                cf -= nf;
                if (!cf) break;
            }
        }
    return getf;
}

那么你外面就不用while了

但是如果是这样写的（没有上面的getf）

int dfs(int x, int cf) {
    if (x == t || !cf) return cf;
    for (...) if (...) {
        int nf = dfs(...);
        if (nf) {
            flow[i] += nf;
            flow[i ^ 1] -= nf;
            return nf;
        }
    }
    return 0;
}

这个dfs就是单路增广的 外面就得有那个while