最小流量制約付き最大流
(include/emthrm/graph/flow/maximum_flow/maximum_flow_with_lower_bound_constraint.hpp)

• View this file on GitHub
• Last update: 2023-02-24 21:17:22+09:00
• Include: #include "emthrm/graph/flow/maximum_flow/maximum_flow_with_lower_bound_constraint.hpp"

計算量

最大流に同じ。

仕様

template <template <typename> class C, typename T>
requires MaximumFlow<C, T>
struct MaximumFlowWithLowerBoundConstraint;

• C：最大流を表す構造体
• T：容量を表す型

メンバ関数

名前	効果・戻り値
explicit MaximumFlowWithLowerBoundConstraint(const int n);	頂点数 $N$ のオブジェクトを構築する。
void add_edge(const int src, const int dst, const T lb, const T ub);	始点 $\mathrm{src}$、終点 $\mathrm{dst}$、容量の下限 $\mathrm{lb}$、上限 $\mathrm{ub}$ の辺を加える。
T solve(const int s, const int t);	始点 $s$ から終点 $t$ までの最大流。ただし存在しないときは $-1$ を返す。

参考文献

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

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/1615/review/4085139/emthrm/C++14

Depends on

• 最大流コンセプト (include/emthrm/graph/flow/maximum_flow/maximum_flow.hpp)

Verified with

• グラフ/フロー/最大流/最小流量制約付き最大流 (test/graph/flow/maximum_flow/maximum_flow_with_lower_bound_constraint.test.cpp)

Code

#ifndef EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_WITH_LOWER_BOUND_CONSTRAINT_HPP_
#define EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_WITH_LOWER_BOUND_CONSTRAINT_HPP_

#include "emthrm/graph/flow/maximum_flow/maximum_flow.hpp"

namespace emthrm {

template <template <typename> class C, typename T>
requires MaximumFlow<C, T>
struct MaximumFlowWithLowerBoundConstraint {
  explicit MaximumFlowWithLowerBoundConstraint(const int n)
      : n(n), sum_lb(0), mf(n + 2) {}

  void add_edge(const int src, const int dst, const T lb, const T ub) {
    mf.add_edge(src, dst, ub - lb);
    mf.add_edge(n, dst, lb);
    mf.add_edge(src, n + 1, lb);
    sum_lb += lb;
  }

  T solve(const int s, const int t) {
    const T a = mf.maximum_flow(n, n + 1);
    const T b = mf.maximum_flow(s, n + 1);
    const T c = mf.maximum_flow(n, t);
    const T d = mf.maximum_flow(s, t);
    return a + b == sum_lb && b == c ? b + d : -1;
  }

 private:
  const int n;
  T sum_lb;
  C<T> mf;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_WITH_LOWER_BOUND_CONSTRAINT_HPP_

#line 1 "include/emthrm/graph/flow/maximum_flow/maximum_flow_with_lower_bound_constraint.hpp"



#line 1 "include/emthrm/graph/flow/maximum_flow/maximum_flow.hpp"
/**
 * @title 最大流コンセプト
 */

#ifndef EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_HPP_
#define EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_HPP_

#include <concepts>
#include <utility>

namespace emthrm {

template <template <typename> class C, typename T>
concept MaximumFlow = requires (C<T> mf) {
  {mf.add_edge(std::declval<int>(), std::declval<int>(), std::declval<T>())}
      -> std::same_as<void>;
  {mf.maximum_flow(std::declval<int>(), std::declval<int>())}
      -> std::same_as<T>;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_HPP_
#line 5 "include/emthrm/graph/flow/maximum_flow/maximum_flow_with_lower_bound_constraint.hpp"

namespace emthrm {

template <template <typename> class C, typename T>
requires MaximumFlow<C, T>
struct MaximumFlowWithLowerBoundConstraint {
  explicit MaximumFlowWithLowerBoundConstraint(const int n)
      : n(n), sum_lb(0), mf(n + 2) {}

  void add_edge(const int src, const int dst, const T lb, const T ub) {
    mf.add_edge(src, dst, ub - lb);
    mf.add_edge(n, dst, lb);
    mf.add_edge(src, n + 1, lb);
    sum_lb += lb;
  }

  T solve(const int s, const int t) {
    const T a = mf.maximum_flow(n, n + 1);
    const T b = mf.maximum_flow(s, n + 1);
    const T c = mf.maximum_flow(n, t);
    const T d = mf.maximum_flow(s, t);
    return a + b == sum_lb && b == c ? b + d : -1;
  }

 private:
  const int n;
  T sum_lb;
  C<T> mf;
};

}  // namespace emthrm

Back to top page