Ford-Fulkerson Algorithm（最大流問題）
(algorithm/Graph/Flow/ford_fulkerson.hpp)

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Include: #include "algorithm/Graph/Flow/ford_fulkerson.hpp"

概要

最大流問題 (maximum-flow problem) を解くアルゴリズム． 1956年に L. R. Ford Jr. と D. R. Fulkerson によって考案された．

フローネットワークと最大流問題の定義

「フローネットワーク (flow network)」とは，各辺 $(u,v) \in E$ が容量 (capacity) $c(u,v) \geq 0 \ (c: V \times V \rightarrow \mathbb{R})$ をもち，また始点 (source) $s \in V$ と終点 (sink) $t \in V$ の2頂点をもつ有向グラフ $G = (V,E)$ のことをいう．便宜上，$(u,v) \notin E$ のとき $c(u,v) = 0$ とみなし，自己ループはないものとする．

$G$ における「フロー (flow)」は，次の2条件を満たす関数 $f: V \times V \rightarrow \mathbb{R}$ である．

容量制限：$0 \leq f(u,v) \leq c(u,v) \ (\forall u, \forall v \in V)$
フロー保存則：$\sum_{v \in V} f(u,v) = \sum_{v \in V} f(v,u) \ (\forall u \in V-{s,t})$

そして，フロー $f$ の値 $\lvert f \rvert$ は次のように定義される（ここでの $\lvert \cdot \rvert$ の表記は絶対値や要素数を表していない）．

\[|f| = \sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s)\]

「最大流問題」とは，与えられたフローネットワーク $G$ に対し，$s$ から $t$ への最大値をもつフローを求める問題である．

アルゴリズムの説明

Ford-Fulkerson algorithm では，次の手続きを反復し，徐々にフローを増やして解に近づけていく．

DFS により，残余ネットワーク上の増加可能パスを探す
発見した増加可能パス上の辺に対してフローを増減させ，残余ネットワークを更新する
残余ネットワーク上から増加可能パスがなくなるまで繰り返す

求める最大のフローを $f^$ とすると，上記手続きの反復回数は高々 $\lvert f^ \rvert$ 回である．各反復時の DFS に $\mathcal{O}(\lvert E \rvert)$ の計算量を要し，全体の計算量は $\mathcal{O}(\lvert f^* \rvert \lvert E \rvert)$ となる．

参考

大槻兼資著. “第16章グラフ (4)：ネットワークフロー”. 問題解決力を鍛える！アルゴリズムとデータ構造. 秋葉拓哉監修. 講談社, 2020, pp.283-309.
“24 最大フロー”. アルゴリズムイントロダクション第4版総合版. 近代科学社, 2024, pp.563-591.
“フローネットワーク”. Wikipedia. https://ja.wikipedia.org/wiki/フローネットワーク.
“最大フロー問題”. Wikipedia. https://ja.wikipedia.org/wiki/最大フロー問題.
“Ford–Fulkerson algorithm”. Wikipedia. https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm.
“フォード・ファルカーソンのアルゴリズム”. Wikipedia. https://ja.wikipedia.org/wiki/フォード・ファルカーソンのアルゴリズム.

問題

“D - Maxflow”. AtCoder Library Practice Contest. AtCoder. https://atcoder.jp/contests/practice2/tasks/practice2_d.

Verified with

verify/aoj-GRL_6_A-ford_fulkerson.test.cpp

Code

#ifndef ALGORITHM_FORD_FULKERSON_HPP
#define ALGORITHM_FORD_FULKERSON_HPP 1

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

namespace algorithm {

template <typename Flow>
class FordFulkerson {
public:
    using flow_type = Flow;

private:
    struct Edge {
        int to;         // to:=(行き先ノード).
        flow_type cap;  // cap:=(容量).
        int rev;        // rev:=(逆辺の位置). m_g[to][rev]が逆辺となる．

        explicit Edge(int to, flow_type cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    int m_vn;                                // m_vn:=(ノード数).
    std::vector<std::vector<Edge>> m_g;      // m_g[v][]:=(ノードvの隣接リスト).
    std::vector<std::pair<int, int>> m_pos;  // m_pos[]:=(i番目の辺の情報). pair of (from, index).

public:
    FordFulkerson() : FordFulkerson(0) {}
    explicit FordFulkerson(int n) : m_vn(n), m_g(n) {
        assert(n >= 0);
    }
    explicit FordFulkerson(int vn, int en) : FordFulkerson(vn) {
        assert(en >= 0);
        m_pos.reserve(en);
    }

    static constexpr flow_type infinity() { return std::numeric_limits<flow_type>::max(); }
    // ノード数を取得する．
    int order() const { return m_vn; }
    // 辺数を取得する．
    int size() const { return m_pos.size(); }
    // 容量capの有向辺を追加する．
    int add_edge(int from, int to, flow_type cap) {
        assert(0 <= from and from < order());
        assert(0 <= to and to < order());
        assert(cap >= 0);
        int i = m_g[from].size(), j = m_g[to].size();
        if(from == to) ++j;
        m_g[from].emplace_back(to, cap, j);
        m_g[to].emplace_back(from, 0, i);
        m_pos.emplace_back(from, i);
        return size() - 1;
    }
    // ノードsからtへの最大流を求める．O(f*|E|).
    flow_type max_flow(int s, int t) { return max_flow(s, t, infinity()); }
    flow_type max_flow(int s, int t, flow_type flow) {
        assert(0 <= s and s < order());
        assert(0 <= t and t < order());
        flow_type res = 0;
        while(res < flow) {
            std::vector<bool> seen(m_vn, false);
            auto dfs = [&](auto self, int v, flow_type flow) -> flow_type {
                if(v == t) return flow;
                seen[v] = true;
                for(Edge &e : m_g[v]) {
                    if(seen[e.to] or e.cap == 0) continue;
                    flow_type res = self(self, e.to, std::min(flow, e.cap));
                    if(res == 0) continue;
                    e.cap -= res;
                    m_g[e.to][e.rev].cap += res;
                    return res;
                }
                return 0;
            };
            flow_type tmp = dfs(dfs, s, flow - res);
            if(tmp == 0) break;
            res += tmp;
        }
        return res;
    }
    // i番目の辺の情報を取得する．
    std::tuple<int, int, flow_type, flow_type> get_edge(int i) const {
        assert(0 <= i and i < size());
        const auto &[from, idx] = m_pos[i];
        const Edge &e = m_g[from][idx];
        return {from, e.to, e.cap + m_g[e.to][e.rev].cap, m_g[e.to][e.rev].cap};  // tuple of (from, to, capacity, flow).
    }
    // 最小カットにより，グラフ上のノードを分割する．
    std::vector<bool> min_cut(int s) const {
        assert(0 <= s and s < order());
        std::vector<bool> res(m_vn, false);
        std::queue<int> que({s});
        while(!que.empty()) {
            int v = que.front();
            que.pop();
            if(res[v]) continue;
            res[v] = true;
            for(const Edge &e : m_g[v]) {
                if(!res[e.to] and e.cap > 0) que.push(e.to);
            }
        }
        return res;
    }
    void reset() {
        for(const auto &[from, idx] : m_pos) {
            Edge &e = m_g[from][idx];
            e.cap += m_g[e.to][e.rev].cap;
            m_g[e.to][e.rev].cap = 0;
        }
    }
};

}  // namespace algorithm

#endif

#line 1 "algorithm/Graph/Flow/ford_fulkerson.hpp"



#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

namespace algorithm {

template <typename Flow>
class FordFulkerson {
public:
    using flow_type = Flow;

private:
    struct Edge {
        int to;         // to:=(行き先ノード).
        flow_type cap;  // cap:=(容量).
        int rev;        // rev:=(逆辺の位置). m_g[to][rev]が逆辺となる．

        explicit Edge(int to, flow_type cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    int m_vn;                                // m_vn:=(ノード数).
    std::vector<std::vector<Edge>> m_g;      // m_g[v][]:=(ノードvの隣接リスト).
    std::vector<std::pair<int, int>> m_pos;  // m_pos[]:=(i番目の辺の情報). pair of (from, index).

public:
    FordFulkerson() : FordFulkerson(0) {}
    explicit FordFulkerson(int n) : m_vn(n), m_g(n) {
        assert(n >= 0);
    }
    explicit FordFulkerson(int vn, int en) : FordFulkerson(vn) {
        assert(en >= 0);
        m_pos.reserve(en);
    }

    static constexpr flow_type infinity() { return std::numeric_limits<flow_type>::max(); }
    // ノード数を取得する．
    int order() const { return m_vn; }
    // 辺数を取得する．
    int size() const { return m_pos.size(); }
    // 容量capの有向辺を追加する．
    int add_edge(int from, int to, flow_type cap) {
        assert(0 <= from and from < order());
        assert(0 <= to and to < order());
        assert(cap >= 0);
        int i = m_g[from].size(), j = m_g[to].size();
        if(from == to) ++j;
        m_g[from].emplace_back(to, cap, j);
        m_g[to].emplace_back(from, 0, i);
        m_pos.emplace_back(from, i);
        return size() - 1;
    }
    // ノードsからtへの最大流を求める．O(f*|E|).
    flow_type max_flow(int s, int t) { return max_flow(s, t, infinity()); }
    flow_type max_flow(int s, int t, flow_type flow) {
        assert(0 <= s and s < order());
        assert(0 <= t and t < order());
        flow_type res = 0;
        while(res < flow) {
            std::vector<bool> seen(m_vn, false);
            auto dfs = [&](auto self, int v, flow_type flow) -> flow_type {
                if(v == t) return flow;
                seen[v] = true;
                for(Edge &e : m_g[v]) {
                    if(seen[e.to] or e.cap == 0) continue;
                    flow_type res = self(self, e.to, std::min(flow, e.cap));
                    if(res == 0) continue;
                    e.cap -= res;
                    m_g[e.to][e.rev].cap += res;
                    return res;
                }
                return 0;
            };
            flow_type tmp = dfs(dfs, s, flow - res);
            if(tmp == 0) break;
            res += tmp;
        }
        return res;
    }
    // i番目の辺の情報を取得する．
    std::tuple<int, int, flow_type, flow_type> get_edge(int i) const {
        assert(0 <= i and i < size());
        const auto &[from, idx] = m_pos[i];
        const Edge &e = m_g[from][idx];
        return {from, e.to, e.cap + m_g[e.to][e.rev].cap, m_g[e.to][e.rev].cap};  // tuple of (from, to, capacity, flow).
    }
    // 最小カットにより，グラフ上のノードを分割する．
    std::vector<bool> min_cut(int s) const {
        assert(0 <= s and s < order());
        std::vector<bool> res(m_vn, false);
        std::queue<int> que({s});
        while(!que.empty()) {
            int v = que.front();
            que.pop();
            if(res[v]) continue;
            res[v] = true;
            for(const Edge &e : m_g[v]) {
                if(!res[e.to] and e.cap > 0) que.push(e.to);
            }
        }
        return res;
    }
    void reset() {
        for(const auto &[from, idx] : m_pos) {
            Edge &e = m_g[from][idx];
            e.cap += m_g[e.to][e.rev].cap;
            m_g[e.to][e.rev].cap = 0;
        }
    }
};

}  // namespace algorithm

Ford-Fulkerson Algorithm（最大流問題） (algorithm/Graph/Flow/ford_fulkerson.hpp)

概要

フローネットワークと最大流問題の定義

アルゴリズムの説明

参考

問題

Verified with

Code

Ford-Fulkerson Algorithm（最大流問題）
(algorithm/Graph/Flow/ford_fulkerson.hpp)