网络流

dinic

代码

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 2e5 + 10, inf = 0x3f3f3f3f;
int head[N], rest[M], to[M], w[M], tot = 1;

void add(int u, int v, int w) {
    to[++ tot] = v, :: w[tot] = w, rest[tot] = head[u], head[u] = tot;
}

int n, m, s, t;

int dis[N];

bool bfs() {
    for(int i = 1 ; i <= n ; ++ i) dis[i] = -1;
    dis[s] = 1;
    queue<int> q; q.push(s);
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int i = head[u] ; i ; i = rest[i]) {
            int v = to[i];
            if(w[i] && dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis[t] != -1;
}

int cur[N];
int dfs(int u, int flow) {
    int use = 0;
    if(u == t || !flow) return flow;
    for(int &i = cur[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(dis[v] == dis[u] + 1) {
            int a = dfs(v, min(flow - use, w[i]));
            use += a;
            w[i] -= a;
            w[i ^ 1] += a;
            if(use == flow) break;
        }
    }
    if(!use) dis[u] = -1;
    return use;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i = 1, u, v, w ; i <= m ; ++ i) {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, 0);
    }
    int ans = 0;
    while(bfs()) {
        for(int i = 1 ; i <= n ; ++ i) cur[i] = head[i];
        ans += dfs(s, inf);
    }
    printf("%d\n", ans);
}

增加退流边

add(u, v, w), add(v, u, 0);

注意反向边是 i ^ 1，所以要 tot = 1 在初始化的时候

构建增广路图

bool bfs() {
    for(int i = 1 ; i <= n ; ++ i) dis[i] = -1;
    dis[s] = 1;
    queue<int> q; q.push(s);
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int i = head[u] ; i ; i = rest[i]) {
            int v = to[i];
            if(w[i] && dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis[t] != -1;
}

通过bfs把可以流过去的边进行拼接，得到一张DAG

不断增广

int dfs(int u, int flow) {
    int use = 0;
    if(u == t || !flow) return flow;
    for(int &i = cur[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(dis[v] == dis[u] + 1) {
            int a = dfs(v, min(flow - use, w[i]));
            use += a;
            w[i] -= a;
            w[i ^ 1] += a;
            if(use == flow) break;
        }
    }
    if(!use) dis[u] = -1;
    return use;
}

这里是把所有可行的增广路都增广了，通过当前弧优化可以加快速度

当前弧优化

for(int &i = cur[u] ; i ; i = rest[i]) { 和 if(use == flow) break;

由于是在DAG上面增广，换句话说，对于一个点，它的出边因为边权限制而无法再流过流量时，之后也不会再从这里流出

故此时将这些在以后的访问中跳过即可

也就是说，对于每个点，“实际”上访问出边是 $O(deg)$ 的

如果当前边还能继续流出流量呢？那最后一次的当前弧就是这里了，之后就会因为 use == flow，也就是说流入的流量用尽了而退出

思考

是否可以通过重制DAG让增广跑得更快？

给定一张网络流图，如何求出一张增广路图使得dfs的总次数最少