cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:heavy_check_mark: Dinic 法
(include/emthrm/graph/flow/maximum_flow/dinic.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_DINIC_HPP_
#define EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_DINIC_HPP_

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

namespace emthrm {

template <typename T>
struct Dinic {
  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 Dinic(const int n) : graph(n), level(n), itr(n) {}

  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) {
      std::fill(level.begin(), level.end(), -1);
      level[s] = 0;
      std::queue<int> que;
      que.emplace(s);
      while (!que.empty()) {
        const int ver = que.front();
        que.pop();
        for (const Edge& e : graph[ver]) {
          if (level[e.dst] == -1 && e.cap > 0) {
            level[e.dst] = level[ver] + 1;
            que.emplace(e.dst);
          }
        }
      }
      if (level[t] == -1) break;
      std::fill(itr.begin(), itr.end(), 0);
      while (limit > 0) {
        const T f = dfs(s, t, limit);
        if (f == 0) break;
        limit -= f;
        res += f;
      }
    }
    return res;
  }

 private:
  std::vector<int> level, itr;

  T dfs(const int ver, const int t, const T flow) {
    if (ver == t) return flow;
    for (; std::cmp_less(itr[ver], graph[ver].size()); ++itr[ver]) {
      Edge& e = graph[ver][itr[ver]];
      if (level[ver] < level[e.dst] && 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_DINIC_HPP_
#line 1 "include/emthrm/graph/flow/maximum_flow/dinic.hpp"



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

namespace emthrm {

template <typename T>
struct Dinic {
  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 Dinic(const int n) : graph(n), level(n), itr(n) {}

  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) {
      std::fill(level.begin(), level.end(), -1);
      level[s] = 0;
      std::queue<int> que;
      que.emplace(s);
      while (!que.empty()) {
        const int ver = que.front();
        que.pop();
        for (const Edge& e : graph[ver]) {
          if (level[e.dst] == -1 && e.cap > 0) {
            level[e.dst] = level[ver] + 1;
            que.emplace(e.dst);
          }
        }
      }
      if (level[t] == -1) break;
      std::fill(itr.begin(), itr.end(), 0);
      while (limit > 0) {
        const T f = dfs(s, t, limit);
        if (f == 0) break;
        limit -= f;
        res += f;
      }
    }
    return res;
  }

 private:
  std::vector<int> level, itr;

  T dfs(const int ver, const int t, const T flow) {
    if (ver == t) return flow;
    for (; std::cmp_less(itr[ver], graph[ver].size()); ++itr[ver]) {
      Edge& e = graph[ver][itr[ver]];
      if (level[ver] < level[e.dst] && 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