C++ Library for Competitive Programming
#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://onlinejudge.u-aizu.ac.jp/solutions/problem/1615/review/4085139/emthrm/C++14
#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