Maximum flow with lower bound
(Mylib/Graph/Flow/max_flow_with_lower_bound.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

• https://snuke.hatenablog.com/entry/2016/07/10/043918
• https://ei1333.github.io/luzhiled/snippets/graph/maxflow-lower-bound.html
• https://tubo28.me/compprog/algorithm/flow_with_lu_bound/

Verified with

• test/aoj/1615/main.test.cpp

Code

#pragma once
#include <cassert>
#include <optional>

namespace haar_lib {
  template <typename Flow>
  class max_flow_with_lower_bound {
    using edge          = typename Flow::edge;
    using capacity_type = typename Flow::capacity_type;

    int N_, S_, T_;
    Flow flow_;
    capacity_type min_sum_;

  public:
    max_flow_with_lower_bound() {}
    max_flow_with_lower_bound(int N) : N_(N), S_(N), T_(N + 1), flow_(N + 2), min_sum_(0) {}

    void add_edge(int from, int to, capacity_type lb, capacity_type ub) {
      assert(0 <= from and from < N_);
      assert(0 <= to and to < N_);
      assert(0 <= lb and lb <= ub);

      flow_.add_edge(from, to, ub - lb);
      flow_.add_edge(from, T_, lb);
      flow_.add_edge(S_, to, lb);

      min_sum_ += lb;
    }

    std::optional<capacity_type> max_flow(int s, int t) {
      assert(0 <= s and s < N_);
      assert(0 <= t and t < N_);

      auto a = flow_.max_flow(S_, T_);
      auto b = flow_.max_flow(s, T_);
      auto c = flow_.max_flow(S_, t);
      auto d = flow_.max_flow(s, t);

      if (a + b == min_sum_ and a + c == min_sum_) return b + d;
      return std::nullopt;
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Graph/Flow/max_flow_with_lower_bound.cpp"
#include <cassert>
#include <optional>

namespace haar_lib {
  template <typename Flow>
  class max_flow_with_lower_bound {
    using edge          = typename Flow::edge;
    using capacity_type = typename Flow::capacity_type;

    int N_, S_, T_;
    Flow flow_;
    capacity_type min_sum_;

  public:
    max_flow_with_lower_bound() {}
    max_flow_with_lower_bound(int N) : N_(N), S_(N), T_(N + 1), flow_(N + 2), min_sum_(0) {}

    void add_edge(int from, int to, capacity_type lb, capacity_type ub) {
      assert(0 <= from and from < N_);
      assert(0 <= to and to < N_);
      assert(0 <= lb and lb <= ub);

      flow_.add_edge(from, to, ub - lb);
      flow_.add_edge(from, T_, lb);
      flow_.add_edge(S_, to, lb);

      min_sum_ += lb;
    }

    std::optional<capacity_type> max_flow(int s, int t) {
      assert(0 <= s and s < N_);
      assert(0 <= t and t < N_);

      auto a = flow_.max_flow(S_, T_);
      auto b = flow_.max_flow(s, T_);
      auto c = flow_.max_flow(S_, t);
      auto d = flow_.max_flow(s, t);

      if (a + b == min_sum_ and a + c == min_sum_) return b + d;
      return std::nullopt;
    }
  };
}  // namespace haar_lib

Back to top page