Flow/FordFulkerson.cpp

Back to top page

• category: Flow
• View this file on GitHub
  • Last commit date: 2020-04-12 12:04:28+09:00

Verified with

• Test/FordFulkerson.test.cpp

Code

template <class T>
struct FordFulkerson {
    struct edge {
        int to;
        int rev;
        T cap;
    };
    vector<vector<edge>> G;
    vector<int> vis;
    FordFulkerson(int n) : G(n), vis(n) {}
    inline void addedge(int u, int v, T c) {
        G[u].emplace_back(edge{v, (int)G[v].size(), c});
        G[v].emplace_back(edge{u, (int)G[u].size() - 1, 0});
    }
    T dfs(int i, const int &t, T flow) {
        if (i == t) return flow;
        vis[i] = 1;
        for (auto &e : G[i]) {
            if (e.cap == 0 || vis[e.to]) continue;
            T x = dfs(e.to, t, min(flow, e.cap));
            if (x > 0) {
                e.cap -= x;
                G[e.to][e.rev].cap += x;
                return x;
            }
        }
        return 0;
    }
    T maxflow(const int &s, const int &t) {
        T res = 0;
        while (1) {
            fill(all(vis), 0);
            T inc = dfs(s, t, INF);
            if (inc == 0) break;
            res += inc;
        }
        return res;
    }
};

#line 1 "Flow/FordFulkerson.cpp"
template <class T>
struct FordFulkerson {
    struct edge {
        int to;
        int rev;
        T cap;
    };
    vector<vector<edge>> G;
    vector<int> vis;
    FordFulkerson(int n) : G(n), vis(n) {}
    inline void addedge(int u, int v, T c) {
        G[u].emplace_back(edge{v, (int)G[v].size(), c});
        G[v].emplace_back(edge{u, (int)G[u].size() - 1, 0});
    }
    T dfs(int i, const int &t, T flow) {
        if (i == t) return flow;
        vis[i] = 1;
        for (auto &e : G[i]) {
            if (e.cap == 0 || vis[e.to]) continue;
            T x = dfs(e.to, t, min(flow, e.cap));
            if (x > 0) {
                e.cap -= x;
                G[e.to][e.rev].cap += x;
                return x;
            }
        }
        return 0;
    }
    T maxflow(const int &s, const int &t) {
        T res = 0;
        while (1) {
            fill(all(vis), 0);
            T inc = dfs(s, t, INF);
            if (inc == 0) break;
            res += inc;
        }
        return res;
    }
};

Back to top page