最小費用 $s$-$t$-フロー (minimum cost $s$-$t$-flow) 最短路反復法 (successive shortest path algorithm) 版
(include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp"

最小費用流 (minimum cost flow)

計算量

最大流の流量を $F$ とおく。

	計算量
最小費用 $s$-$t$-フロー 最短路反復法版	$O(\lvert V \rvert \lvert E \rvert + F \lvert E \rvert \log{\lvert V \rvert})$
最小費用 $\boldsymbol{b}$-フロー 最短路反復法版	コスト負の辺の容量の総和を $F^{\prime}$ とおくと $O((F + F^{\prime})\lvert E \rvert \log{\lvert V \rvert})$。

仕様

最小費用 $s$-$t$-フロー 最短路反復法版

template <typename T, typename U>
struct MinimumCostSTFlow;

• T：容量を表す型
• U：コストを表す型

メンバ変数

名前	説明
const U uinf	$\infty$
std::vector<std::vector<Edge>> graph	残余グラフ

メンバ関数

名前	効果・戻り値	備考
explicit MinimumCostSTFlow(const int n, const U uinf = std::numeric_limits<U>::max());	頂点数 $N$ のオブジェクトを構築する。
void add_edge(const int src, const int dst, const T cap, const U cost);	始点 $\mathrm{src}$、終点 $\mathrm{dst}$、容量 $\mathrm{cap}$、コスト $\mathrm{cost}$ の辺を加える。
U solve(const int s, const int t, T flow);	始点 $s$ から終点 $t$ まで流量 $\mathrm{flow}$ のフローを流すときの最小コスト。ただし流せないときは uinf を返す。
U solve(const int s, const int t);	始点 $s$ から終点 $t$ まで流量任意のフローを流すときの最小コスト	流量は $\mathrm{tinf} - \mathrm{flow}$ である。
std::pair<T, U> minimum_cost_maximum_flow(const int s, const int t, const T flow);	始点 $s$ から終点 $t$ まで流量 $\mathrm{flow}$ 以下のフローを流すときの最小費用最大流。最大流と最小費用の組を返す。

メンバ型

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

struct Edge;

メンバ変数

名前	説明
int dst	終点
int rev	頂点 $\mathrm{dst}$ における逆辺のインデックス
T cap	残りの容量
U cost	流量 $1$ のフローを流すときのコスト

メンバ関数

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

最小費用 $\boldsymbol{b}$-フロー 最短路反復法版

template <typename T, typename U>
struct MinimumCostBFlow;

• T：容量を表す型
• U：コストを表す型

メンバ変数

名前	説明
const U uinf	$\infty$
std::vector<std::vector<Edge>> graph	残余グラフ

メンバ関数

名前	効果・戻り値
explicit MinimumCostBFlow(const int n, const U uinf = std::numeric_limits<U>::max());	頂点数 $N$ のオブジェクトを構築する。
void add_edge(int src, int dst, const T cap, U cost);	始点 $\mathrm{src}$、終点 $\mathrm{dst}$、容量 $\mathrm{cap}$、コスト $\mathrm{cost}$ の辺を加える。
void supply_or_demand(const int ver, const T amount);	$b_{\mathrm{ver}} \gets b_{\mathrm{ver}} + \mathrm{amount}$
U solve();	最小費用循環流。ただし流せないときは uinf を返す。
U solve(const int s, const int t, const T flow);	始点 $s$ から終点 $t$ まで流量 $\mathrm{flow}$ のフローを流すときの最小コスト。ただし流せないときは uinf を返す。

メンバ型

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

struct Edge;

メンバ変数

名前	説明
int dst	終点
int rev	頂点 $\mathrm{dst}$ における逆辺のインデックス
T cap	残りの容量
U cost	流量 $1$ のフローを流すときのコスト

メンバ関数

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

注意

流量正の辺の合計コストの和を最小化する問題を最小費用流で解くことはできない。

参考文献

• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，pp.199-205，マイナビ出版（2012）

最小費用 $s$-$t$-フロー 最短路反復法版

• Jack Edmonds, Richard M. Karp: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM, Vol. 19, No. 2, pp. 248–264 (1972). https://doi.org/10.1145/321694.321699
• http://sigma425.hatenablog.com/entry/2014/10/12/122018

最小費用 $\boldsymbol{b}$-フロー 最短路反復法版

• https://snuke.hatenablog.com/entry/2017/06/07/115821

TODO

• 容量スケーリング
  • https://misawa.github.io/others/flow/lets_use_capacity_scaling.html
• 最小費用 $\boldsymbol{b}$-フロー
  • https://misawa.github.io/others/flow/library_design.html
  • https://twitter.com/Mi_Sawa/status/1283768916775321601
  • https://noshi91.hatenablog.com/entry/2021/12/15/012019
  • https://judge.yosupo.jp/problem/min_cost_b_flow
• グラフにコスト負の閉路が存在するとき

Submissons

• 最小費用 $s$-$t$-フロー 最短路反復法版
  • solve(s, t, flow)
  • solve(s, t)
  • minimum_cost_maximum_flow(s, t, flow)
• 最小費用 $\boldsymbol{b}$-フロー 最短路反復法版

Required by

• 二部グラフの重み付き最大マッチング (include/emthrm/graph/flow/matching/weighted_bipartite_matching.hpp)

Verified with

• グラフ/フロー/マッチング/二部グラフの重み付き最大マッチング (test/graph/flow/matching/weighted_bipartite_matching.test.cpp)
• グラフ/フロー/最小費用流/最小費用 $s$-$t$-フロー 最短路反復法版 (test/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.1.test.cpp)
• グラフ/フロー/最小費用流/最小費用 $s$-$t$-フロー 最短路反復法版（任意流量） (test/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.2.test.cpp)
• グラフ/フロー/最小費用流/最小費用 $s$-$t$-フロー 最短路反復法版（最小費用最大流） (test/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.3.test.cpp)
• 数学/多倍長整数 (test/math/bigint.01.test.cpp)

Code

#ifndef EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_S_T_FLOW_HPP_
#define EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_S_T_FLOW_HPP_

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

namespace emthrm {

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

  const U uinf;
  std::vector<std::vector<Edge>> graph;

  explicit MinimumCostSTFlow(const int n,
                             const U uinf = std::numeric_limits<U>::max())
      : uinf(uinf), graph(n), tinf(std::numeric_limits<T>::max()), n(n),
        has_negative_edge(false), prev_v(n, -1), prev_e(n, -1), dist(n),
        potential(n, 0) {}

  void add_edge(const int src, const int dst, const T cap, const U cost) {
    has_negative_edge |= cost < 0;
    graph[src].emplace_back(dst, cap, cost, graph[dst].size());
    graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1);
  }

  U solve(const int s, const int t, T flow) {
    if (flow == 0) [[unlikely]] return 0;
    U res = 0;
    has_negative_edge ? bellman_ford(s) : dijkstra(s);
    while (true) {
      if (dist[t] == uinf) return uinf;
      res += calc(s, t, &flow);
      if (flow == 0) break;
      dijkstra(s);
    }
    return res;
  }

  U solve(const int s, const int t) {
    U res = 0;
    T flow = tinf;
    bellman_ford(s);
    while (potential[t] < 0 && dist[t] != uinf) {
      res += calc(s, t, &flow);
      dijkstra(s);
    }
    return res;
  }

  std::pair<T, U> minimum_cost_maximum_flow(const int s, const int t,
                                            const T flow) {
    if (flow == 0) [[unlikely]] return {0, 0};
    T f = flow;
    U cost = 0;
    has_negative_edge ? bellman_ford(s) : dijkstra(s);
    while (dist[t] != uinf) {
      cost += calc(s, t, &f);
      if (f == 0) break;
      dijkstra(s);
    }
    return {flow - f, cost};
  }

 private:
  const T tinf;
  const int n;
  bool has_negative_edge;
  std::vector<int> prev_v, prev_e;
  std::vector<U> dist, potential;
  std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>,
                      std::greater<std::pair<U, int>>> que;

  void bellman_ford(const int s) {
    std::fill(dist.begin(), dist.end(), uinf);
    dist[s] = 0;
    bool is_updated = true;
    for (int step = 0; step < n && is_updated; ++step) {
      is_updated = false;
      for (int i = 0; i < n; ++i) {
        if (dist[i] == uinf) continue;
        for (int j = 0; std::cmp_less(j, graph[i].size()); ++j) {
          const Edge& e = graph[i][j];
          if (e.cap > 0 && dist[e.dst] > dist[i] + e.cost) {
            dist[e.dst] = dist[i] + e.cost;
            prev_v[e.dst] = i;
            prev_e[e.dst] = j;
            is_updated = true;
          }
        }
      }
    }
    assert(!is_updated);
    for (int i = 0; i < n; ++i) {
      if (dist[i] != uinf) potential[i] += dist[i];
    }
  }

  void dijkstra(const int s) {
    std::fill(dist.begin(), dist.end(), uinf);
    dist[s] = 0;
    que.emplace(0, s);
    while (!que.empty()) {
      const auto [d, ver] = que.top();
      que.pop();
      if (dist[ver] < d) continue;
      for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {
        const Edge& e = graph[ver][i];
        const U nxt = dist[ver] + e.cost + potential[ver] - potential[e.dst];
        if (e.cap > 0 && dist[e.dst] > nxt) {
          dist[e.dst] = nxt;
          prev_v[e.dst] = ver;
          prev_e[e.dst] = i;
          que.emplace(dist[e.dst], e.dst);
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      if (dist[i] != uinf) potential[i] += dist[i];
    }
  }

  U calc(const int s, const int t, T* flow) {
    T f = *flow;
    for (int v = t; v != s; v = prev_v[v]) {
      f = std::min(f, graph[prev_v[v]][prev_e[v]].cap);
    }
    *flow -= f;
    for (int v = t; v != s; v = prev_v[v]) {
      Edge& e = graph[prev_v[v]][prev_e[v]];
      e.cap -= f;
      graph[v][e.rev].cap += f;
    }
    return potential[t] * f;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_S_T_FLOW_HPP_

#line 1 "include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_s-t-flow.hpp"



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

namespace emthrm {

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

  const U uinf;
  std::vector<std::vector<Edge>> graph;

  explicit MinimumCostSTFlow(const int n,
                             const U uinf = std::numeric_limits<U>::max())
      : uinf(uinf), graph(n), tinf(std::numeric_limits<T>::max()), n(n),
        has_negative_edge(false), prev_v(n, -1), prev_e(n, -1), dist(n),
        potential(n, 0) {}

  void add_edge(const int src, const int dst, const T cap, const U cost) {
    has_negative_edge |= cost < 0;
    graph[src].emplace_back(dst, cap, cost, graph[dst].size());
    graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1);
  }

  U solve(const int s, const int t, T flow) {
    if (flow == 0) [[unlikely]] return 0;
    U res = 0;
    has_negative_edge ? bellman_ford(s) : dijkstra(s);
    while (true) {
      if (dist[t] == uinf) return uinf;
      res += calc(s, t, &flow);
      if (flow == 0) break;
      dijkstra(s);
    }
    return res;
  }

  U solve(const int s, const int t) {
    U res = 0;
    T flow = tinf;
    bellman_ford(s);
    while (potential[t] < 0 && dist[t] != uinf) {
      res += calc(s, t, &flow);
      dijkstra(s);
    }
    return res;
  }

  std::pair<T, U> minimum_cost_maximum_flow(const int s, const int t,
                                            const T flow) {
    if (flow == 0) [[unlikely]] return {0, 0};
    T f = flow;
    U cost = 0;
    has_negative_edge ? bellman_ford(s) : dijkstra(s);
    while (dist[t] != uinf) {
      cost += calc(s, t, &f);
      if (f == 0) break;
      dijkstra(s);
    }
    return {flow - f, cost};
  }

 private:
  const T tinf;
  const int n;
  bool has_negative_edge;
  std::vector<int> prev_v, prev_e;
  std::vector<U> dist, potential;
  std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>,
                      std::greater<std::pair<U, int>>> que;

  void bellman_ford(const int s) {
    std::fill(dist.begin(), dist.end(), uinf);
    dist[s] = 0;
    bool is_updated = true;
    for (int step = 0; step < n && is_updated; ++step) {
      is_updated = false;
      for (int i = 0; i < n; ++i) {
        if (dist[i] == uinf) continue;
        for (int j = 0; std::cmp_less(j, graph[i].size()); ++j) {
          const Edge& e = graph[i][j];
          if (e.cap > 0 && dist[e.dst] > dist[i] + e.cost) {
            dist[e.dst] = dist[i] + e.cost;
            prev_v[e.dst] = i;
            prev_e[e.dst] = j;
            is_updated = true;
          }
        }
      }
    }
    assert(!is_updated);
    for (int i = 0; i < n; ++i) {
      if (dist[i] != uinf) potential[i] += dist[i];
    }
  }

  void dijkstra(const int s) {
    std::fill(dist.begin(), dist.end(), uinf);
    dist[s] = 0;
    que.emplace(0, s);
    while (!que.empty()) {
      const auto [d, ver] = que.top();
      que.pop();
      if (dist[ver] < d) continue;
      for (int i = 0; std::cmp_less(i, graph[ver].size()); ++i) {
        const Edge& e = graph[ver][i];
        const U nxt = dist[ver] + e.cost + potential[ver] - potential[e.dst];
        if (e.cap > 0 && dist[e.dst] > nxt) {
          dist[e.dst] = nxt;
          prev_v[e.dst] = ver;
          prev_e[e.dst] = i;
          que.emplace(dist[e.dst], e.dst);
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      if (dist[i] != uinf) potential[i] += dist[i];
    }
  }

  U calc(const int s, const int t, T* flow) {
    T f = *flow;
    for (int v = t; v != s; v = prev_v[v]) {
      f = std::min(f, graph[prev_v[v]][prev_e[v]].cap);
    }
    *flow -= f;
    for (int v = t; v != s; v = prev_v[v]) {
      Edge& e = graph[prev_v[v]][prev_e[v]];
      e.cap -= f;
      graph[v][e.rev].cap += f;
    }
    return potential[t] * f;
  }
};

}  // namespace emthrm

Back to top page