最小費用 $\boldsymbol{b}$-フロー (minimum cost $\boldsymbol{b}$-flow) 最短路反復法 (successive shortest path algorithm) 版
(include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-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_b-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$-フロー最短路反復法版
最小費用 $\boldsymbol{b}$-フロー最短路反復法版

Verified with

グラフ/フロー/最小費用流/最小流量制約付き最小費用流 (test/graph/flow/minimum_cost_flow/minimum_cost_flow_with_lower_bound_constraint.test.cpp)

Code

#ifndef EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_B_FLOW_HPP_
#define EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_B_FLOW_HPP_

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

namespace emthrm {

template <typename T, typename U>
struct MinimumCostBFlow {
  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 MinimumCostBFlow(const int n,
                            const U uinf = std::numeric_limits<U>::max())
      : uinf(uinf), graph(n + 2), n(n), res(0), b(n + 2, 0) {}

  void add_edge(int src, int dst, const T cap, U cost) {
    if (cost < 0) {
      b[src] -= cap;
      b[dst] += cap;
      res += cost * cap;
      std::swap(src, dst);
      cost = -cost;
    }
    graph[src].emplace_back(dst, cap, cost, graph[dst].size());
    graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1);
  }

  void supply_or_demand(const int ver, const T amount) { b[ver] += amount; }

  U solve() {
    assert(std::reduce(b.begin(), b.end(), static_cast<T>(0)) == 0);
    T flow = 0;
    for (int i = 0; i < n; ++i) {
      if (b[i] > 0) {
        add_edge(n, i, b[i], 0);
        flow += b[i];
      } else if (b[i] < 0) {
        add_edge(i, n + 1, -b[i], 0);
      }
    }
    std::vector<int> prev_v(n + 2, -1), prev_e(n + 2, -1);
    std::vector<U> dist(n + 2), potential(n + 2, 0);
    std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>,
                        std::greater<std::pair<U, int>>> que;
    while (flow > 0) {
      std::fill(dist.begin(), dist.end(), uinf);
      dist[n] = 0;
      que.emplace(0, n);
      while (!que.empty()) {
        const auto [d, ver] = que.top();
        que.pop();
        if (d > dist[ver]) 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);
          }
        }
      }
      if (dist[n + 1] == uinf) return uinf;
      for (int i = 0; i < n + 2; ++i) {
        if (dist[i] != uinf) potential[i] += dist[i];
      }
      T f = flow;
      for (int v = n + 1; v != n; v = prev_v[v]) {
        f = std::min(f, graph[prev_v[v]][prev_e[v]].cap);
      }
      flow -= f;
      res += potential[n + 1] * f;
      for (int v = n + 1; v != n; v = prev_v[v]) {
        Edge& e = graph[prev_v[v]][prev_e[v]];
        e.cap -= f;
        graph[v][e.rev].cap += f;
      }
    }
    return res;
  }

  U solve(const int s, const int t, const T flow) {
    supply_or_demand(s, flow);
    supply_or_demand(t, -flow);
    return solve();
  }

 private:
  int n;
  U res;
  std::vector<T> b;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_FLOW_MINIMUM_COST_FLOW_MINIMUM_COST_B_FLOW_HPP_

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



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

namespace emthrm {

template <typename T, typename U>
struct MinimumCostBFlow {
  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 MinimumCostBFlow(const int n,
                            const U uinf = std::numeric_limits<U>::max())
      : uinf(uinf), graph(n + 2), n(n), res(0), b(n + 2, 0) {}

  void add_edge(int src, int dst, const T cap, U cost) {
    if (cost < 0) {
      b[src] -= cap;
      b[dst] += cap;
      res += cost * cap;
      std::swap(src, dst);
      cost = -cost;
    }
    graph[src].emplace_back(dst, cap, cost, graph[dst].size());
    graph[dst].emplace_back(src, 0, -cost, graph[src].size() - 1);
  }

  void supply_or_demand(const int ver, const T amount) { b[ver] += amount; }

  U solve() {
    assert(std::reduce(b.begin(), b.end(), static_cast<T>(0)) == 0);
    T flow = 0;
    for (int i = 0; i < n; ++i) {
      if (b[i] > 0) {
        add_edge(n, i, b[i], 0);
        flow += b[i];
      } else if (b[i] < 0) {
        add_edge(i, n + 1, -b[i], 0);
      }
    }
    std::vector<int> prev_v(n + 2, -1), prev_e(n + 2, -1);
    std::vector<U> dist(n + 2), potential(n + 2, 0);
    std::priority_queue<std::pair<U, int>, std::vector<std::pair<U, int>>,
                        std::greater<std::pair<U, int>>> que;
    while (flow > 0) {
      std::fill(dist.begin(), dist.end(), uinf);
      dist[n] = 0;
      que.emplace(0, n);
      while (!que.empty()) {
        const auto [d, ver] = que.top();
        que.pop();
        if (d > dist[ver]) 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);
          }
        }
      }
      if (dist[n + 1] == uinf) return uinf;
      for (int i = 0; i < n + 2; ++i) {
        if (dist[i] != uinf) potential[i] += dist[i];
      }
      T f = flow;
      for (int v = n + 1; v != n; v = prev_v[v]) {
        f = std::min(f, graph[prev_v[v]][prev_e[v]].cap);
      }
      flow -= f;
      res += potential[n + 1] * f;
      for (int v = n + 1; v != n; v = prev_v[v]) {
        Edge& e = graph[prev_v[v]][prev_e[v]];
        e.cap -= f;
        graph[v][e.rev].cap += f;
      }
    }
    return res;
  }

  U solve(const int s, const int t, const T flow) {
    supply_or_demand(s, flow);
    supply_or_demand(t, -flow);
    return solve();
  }

 private:
  int n;
  U res;
  std::vector<T> b;
};

}  // namespace emthrm

最小費用 $\boldsymbol{b}$-フロー (minimum cost $\boldsymbol{b}$-flow) 最短路反復法 (successive shortest path algorithm) 版 (include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp)

最小費用流 (minimum cost flow)

計算量

仕様

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

メンバ変数

メンバ関数

メンバ型

メンバ変数

メンバ関数

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

メンバ変数

メンバ関数

メンバ型

メンバ変数

メンバ関数

注意

参考文献

TODO

Submissons

Verified with

Code

最小費用 $\boldsymbol{b}$-フロー (minimum cost $\boldsymbol{b}$-flow) 最短路反復法 (successive shortest path algorithm) 版
(include/emthrm/graph/flow/minimum_cost_flow/minimum_cost_b-flow.hpp)

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

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