cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:heavy_check_mark: Ford–Fulkerson 法
(include/emthrm/graph/flow/maximum_flow/ford-fulkerson.hpp)

最大流 (maximum flow)

ある始点からある終点までのフローの最大値である。

最大フロー最小カット定理より最小カットと一致する。

時間計算量

アルゴリズム 時間計算量
Ford–Fulkerson 法 最大流を $F$ とおくと $O(F \lvert E \rvert)$
Dinic 法 最大流を $F$ とおくと $O\left(\min \left\lbrace {\lvert V \rvert}^2 \lvert E \rvert,\ F \lvert E \rvert,\ {\lvert E \rvert}^{3/2} \max_{e \in E} C_e,\ \sqrt{\lvert V \rvert} \lvert E \rvert \max_{v \in V} \min \left\lbrace \sum_{e \in \delta^-(v) \subset E} C_e, \sum_{e \in \delta^+(v) \subset E} C_e \right\rbrace \right\rbrace\right)$

仕様

Ford–Fulkerson 法

template <typename T>
struct FordFulkerson;

メンバ変数

名前 説明
std::vector<std::vector<Edge>> graph 残余グラフ

メンバ関数

名前 効果・戻り値 備考
explicit FordFulkerson(const int n); 頂点数 $N$ のオブジェクトを構築する。  
void add_edge(const int src, const int dst, const T cap); 容量 $\mathrm{cap}$ の辺 $(\mathrm{src}, \mathrm{dst})$ を追加する。  
T maximum_flow(const int s, const int t, T limit = std::numeric_limits<T>::max()); 上限を $\mathrm{limit}$ とした始点 $s$ から終点 $t$ までの最大流 容量が整数でなければ、停止しないときがある。

メンバ型

名前 説明
Edge 辺を表す構造体 
struct Edge;

メンバ変数

名前 説明
int dst 終点
int rev 頂点 $\mathrm{dst}$ における逆辺のインデックス
T cap 残りの容量

メンバ関数

名前 効果
explicit Edge(const int dst, const T cap, const int rev); コンストラクタ

Dinic 法

template <typename T>
struct Dinic;

メンバ変数

名前 説明
std::vector<std::vector<Edge>> graph 残余グラフ

メンバ関数

名前 効果・戻り値
explicit Dinic(const int n); 頂点数 $N$ のオブジェクトを構築する。
void add_edge(const int src, const int dst, const T cap); 容量 $\mathrm{cap}$ の辺 $(\mathrm{src}, \mathrm{dst})$ を追加する。
T maximum_flow(const int s, const int t, T limit = std::numeric_limits<T>::max()); 上限を $\mathrm{limit}$ とした始点 $s$ から終点 $t$ までの最大流

メンバ型

名前 説明
Edge 辺を表す構造体 
struct Edge;

メンバ変数

名前 説明
int dst 終点
int rev 頂点 $\mathrm{dst}$ における逆辺のインデックス
T cap 残りの容量

メンバ関数

名前 効果
explicit Edge(const int dst, const T cap, const int rev); コンストラクタ

特殊ケース

参考文献

Ford–Fulkerson 法

Dinic 法

TODO

Submissons

Verified with

Code

#ifndef EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_FORD_FULKERSON_HPP_
#define EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_FORD_FULKERSON_HPP_

#include <algorithm>
#include <limits>
#include <vector>

namespace emthrm {

template <typename T>
struct FordFulkerson {
  struct Edge {
    int dst, rev;
    T cap;
    explicit Edge(const int dst, const T cap, const int rev)
        : dst(dst), rev(rev), cap(cap) {}
  };

  std::vector<std::vector<Edge>> graph;

  explicit FordFulkerson(const int n)
      : graph(n), timestamp(0), is_used(n, -1) {}

  void add_edge(const int src, const int dst, const T cap) {
    graph[src].emplace_back(dst, cap, graph[dst].size());
    graph[dst].emplace_back(src, 0, graph[src].size() - 1);
  }

  T maximum_flow(const int s, const int t,
                 T limit = std::numeric_limits<T>::max()) {
    T res = 0;
    while (limit > 0) {
      const T tmp = dfs(s, t, limit);
      ++timestamp;
      if (tmp == 0) break;
      limit -= tmp;
      res += tmp;
    }
    return res;
  }

 private:
  int timestamp;
  std::vector<int> is_used;

  T dfs(const int ver, const int t, const T flow) {
    if (ver == t) return flow;
    is_used[ver] = timestamp;
    for (Edge& e : graph[ver]) {
      if (is_used[e.dst] < timestamp && e.cap > 0) {
        const T tmp = dfs(e.dst, t, std::min(flow, e.cap));
        if (tmp > 0) {
          e.cap -= tmp;
          graph[e.dst][e.rev].cap += tmp;
          return tmp;
        }
      }
    }
    return 0;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_FORD_FULKERSON_HPP_
#line 1 "include/emthrm/graph/flow/maximum_flow/ford-fulkerson.hpp"



#include <algorithm>
#include <limits>
#include <vector>

namespace emthrm {

template <typename T>
struct FordFulkerson {
  struct Edge {
    int dst, rev;
    T cap;
    explicit Edge(const int dst, const T cap, const int rev)
        : dst(dst), rev(rev), cap(cap) {}
  };

  std::vector<std::vector<Edge>> graph;

  explicit FordFulkerson(const int n)
      : graph(n), timestamp(0), is_used(n, -1) {}

  void add_edge(const int src, const int dst, const T cap) {
    graph[src].emplace_back(dst, cap, graph[dst].size());
    graph[dst].emplace_back(src, 0, graph[src].size() - 1);
  }

  T maximum_flow(const int s, const int t,
                 T limit = std::numeric_limits<T>::max()) {
    T res = 0;
    while (limit > 0) {
      const T tmp = dfs(s, t, limit);
      ++timestamp;
      if (tmp == 0) break;
      limit -= tmp;
      res += tmp;
    }
    return res;
  }

 private:
  int timestamp;
  std::vector<int> is_used;

  T dfs(const int ver, const int t, const T flow) {
    if (ver == t) return flow;
    is_used[ver] = timestamp;
    for (Edge& e : graph[ver]) {
      if (is_used[e.dst] < timestamp && e.cap > 0) {
        const T tmp = dfs(e.dst, t, std::min(flow, e.cap));
        if (tmp > 0) {
          e.cap -= tmp;
          graph[e.dst][e.rev].cap += tmp;
          return tmp;
        }
      }
    }
    return 0;
  }
};

}  // namespace emthrm
Back to top page