Maximum Flow - Dinic Algorithm

dinic.cc

typedef int F;
#define MAXE 50000
#define MAXV 20000
#define F_INF 1000000

struct MaxFlow {
    int V, E;
    int start[MAXV], next[MAXE], v[MAXE];
    int used[MAXV], level[MAXV];
    F cap[MAXE], flow[MAXE];

    MaxFlow(int n) {
        int i;
        V = n; E = 0;
        memset(start, -1, sizeof(start));
    }

    void add_edge(int x, int y, F c) {
        cap[E] = c; flow[E] = 0; v[E] = y; next[E] = start[x]; start[x] = E; ++ E;
        cap[E] = 0; flow[E] = 0; v[E] = x; next[E] = start[y]; start[y] = E; ++ E;
    }

    bool bfs(int s, int t) {
        memset(level, -1, sizeof(level));
        queue<int> q;
        q.push(s); level[s] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i = start[x]; i != -1; i = next[i])
                if (level[v[i]] == -1 && cap[i] > flow[i]) {
                    q.push(v[i]);
                    level[v[i]] = level[x] + 1;
                }
        }
        return (level[t] != -1);
    }

    F dfs(int s, int t, F f) {
        if (s == t) return f;
        for (int &i = used[s]; i != -1; i = next[i])
            //if (level[v[i]] > level[s] && cap[i] > flow[i]) { // should be same
            if (level[v[i]] == level[s] + 1 && cap[i] > flow[i]) {
                F temp = dfs(v[i], t, min(f, cap[i] - flow[i]));
                if (temp > 0) {
                    flow[i] += temp; flow[i^1] -= temp;
                    return temp;
                }
            }
        return 0;
    }

    F maxflow(int s, int t) {
        while (bfs(s, t)) {
            for (int i = 0; i < V; ++ i)
                used[i] = start[i];
            while (dfs(s, t, F_INF) != 0);
        }
        F ret = 0;
        for (int i = start[s]; i != -1; i = next[i])
            ret += flow[i];
        return ret;
    }
};

dinic_oo.cc

const int MAXN = 105;

typedef int F;
const int MAXV = 4 * MAXN;
const int MAXE = MAXV * MAXV * 2;
const int F_INF = 10000000;

class MaxFlow {
public:
    int V, E;

    MaxFlow(int V) : V(V), E(0) {
        memset(start, -1, sizeof(start));
    }

    void add_edge(int x, int y, F c) {
        cap[E] = c; flow[E] = 0; v[E] = y; next[E] = start[x]; start[x] = E; ++ E;
        cap[E] = 0; flow[E] = 0; v[E] = x; next[E] = start[y]; start[y] = E; ++ E;
    }

    bool BFS(int, int);
    F DFS(int, int, F);
    F maxflow(int, int);

    vector<pair<int, int>> get_flows();

private:
    int start[MAXV], next[MAXE], v[MAXE];
    int used[MAXV], level[MAXV];
    F cap[MAXE], flow[MAXE];
};

vector<pair<int, int>> MaxFlow::get_flows() {
    vector<pair<int, int>> ret;
    for (int i = 0; i < V; ++ i)
        for (int j = start[i]; j != -1; j = next[j])
            if (flow[j] > 0)
                ret.push_back({i, v[j]});
    return ret;
}

bool MaxFlow::BFS(int s, int t) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    q.push(s); level[s] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = start[x]; i != -1; i = next[i])
            if (level[v[i]] == -1 && cap[i] > flow[i]) {
                q.push(v[i]);
                level[v[i]] = level[x] + 1;
            }
    }
    return (level[t] != -1);
}

F MaxFlow::DFS(int s, int t, F f) {
    if (s == t) return f;
    for (int &i = used[s]; i != -1; i = next[i])
        //if (level[v[i]] > level[s] && cap[i] > flow[i]) { // should be same
        if (level[v[i]] == level[s] + 1 && cap[i] > flow[i]) {
            F temp = DFS(v[i], t, min(f, cap[i] - flow[i]));
            if (temp > 0) {
                flow[i] += temp; flow[i^1] -= temp;
                return temp;
            }
        }
    return 0;
}

F MaxFlow::maxflow(int s, int t) {
    while (BFS(s, t)) {
        for (int i = 0; i < V; ++ i)
            used[i] = start[i];
        while (DFS(s, t, F_INF) != 0);
    }
    F ret = 0;
    for (int i = start[s]; i != -1; i = next[i])
        ret += flow[i];
    return ret;
}