FordFulkerson法
(graph/maximumflow/fordfulkerson.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/maximumflow/fordfulkerson.hpp"
• Link: http://yosupo.hatenablog.com/entry/2015/03/31/134336

概要

最大流を求めるアルゴリズム.

計算量

$O(EF)$

• $F$ : 最大フロー

使用例

• FordFulkerson<int> ff(V) : $V$頂点のグラフを定義.
  • 容量の型 : int
• ff.add_arc(u, v, c) : $u$から$v$に容量$c$の有向辺を張る.
• ff.add_edge(u, v, c) : $u$から$v$に容量$c$の無向辺を張る.
• ff.max_flow(s, t) : $s$から$t$への最大流を求める.

Verified with

• test/aoj/GRL_6_A.fordfulkerson.test.cpp

Code

/**
* @brief FordFulkerson法
* @docs docs/graph/maximumflow/fordfulkerson.md
* @see http://yosupo.hatenablog.com/entry/2015/03/31/134336
* @note O(E * F) (F : 最大フロー)
*/

template <typename T>
struct FordFulkerson {
    struct CapEdge {
        int to, rev;
        T cap;
        CapEdge() {}
        CapEdge(int t, int r, T c)
            : to(t), rev(r), cap(c) {}
        operator int() const { return to; }
    };
    const T INF;
    int timestamp;
    vector<int> used;
    vector<vector<CapEdge>> graph;
    FordFulkerson(int n)
        : INF(numeric_limits<T>::max()), timestamp(0), used(n, -1), graph(n) {}
    void add_arc(int a, int b, T c) {
        graph[a].emplace_back(b, (int)graph[b].size(), c);
        graph[b].emplace_back(a, (int)graph[a].size() - 1, 0);
    }
    void add_edge(int a, int b, T c) {
        graph[a].emplace_back(b, (int)graph[b].size(), c);
        graph[b].emplace_back(a, (int)graph[a].size() - 1, c);
    }
    T dfs(int idx, const int t, T flw) {
        if (idx == t) return flw;
        used[idx] = timestamp;
        for (auto& nxt : graph[idx]) {
            if (nxt.cap > 0 and used[nxt] != timestamp) {
                T d = dfs(nxt, t, min(flw, nxt.cap));
                if (d > 0) {
                    nxt.cap -= d;
                    graph[nxt][nxt.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    T max_flow(int s, int t) {
        T ret = 0;
        for (T tmp; (tmp = dfs(s, t, INF)) > 0; ++timestamp) ret += tmp;
        return ret;
    }
};

#line 1 "graph/maximumflow/fordfulkerson.hpp"
/**
* @brief FordFulkerson法
* @docs docs/graph/maximumflow/fordfulkerson.md
* @see http://yosupo.hatenablog.com/entry/2015/03/31/134336
* @note O(E * F) (F : 最大フロー)
*/

template <typename T>
struct FordFulkerson {
    struct CapEdge {
        int to, rev;
        T cap;
        CapEdge() {}
        CapEdge(int t, int r, T c)
            : to(t), rev(r), cap(c) {}
        operator int() const { return to; }
    };
    const T INF;
    int timestamp;
    vector<int> used;
    vector<vector<CapEdge>> graph;
    FordFulkerson(int n)
        : INF(numeric_limits<T>::max()), timestamp(0), used(n, -1), graph(n) {}
    void add_arc(int a, int b, T c) {
        graph[a].emplace_back(b, (int)graph[b].size(), c);
        graph[b].emplace_back(a, (int)graph[a].size() - 1, 0);
    }
    void add_edge(int a, int b, T c) {
        graph[a].emplace_back(b, (int)graph[b].size(), c);
        graph[b].emplace_back(a, (int)graph[a].size() - 1, c);
    }
    T dfs(int idx, const int t, T flw) {
        if (idx == t) return flw;
        used[idx] = timestamp;
        for (auto& nxt : graph[idx]) {
            if (nxt.cap > 0 and used[nxt] != timestamp) {
                T d = dfs(nxt, t, min(flw, nxt.cap));
                if (d > 0) {
                    nxt.cap -= d;
                    graph[nxt][nxt.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    T max_flow(int s, int t) {
        T ret = 0;
        for (T tmp; (tmp = dfs(s, t, INF)) > 0; ++timestamp) ret += tmp;
        return ret;
    }
};

Back to top page