流量の下限制約付き最大流
概要
普通の最大流では 0 以上容量以下の任意の流用を流せるが，そこに「〜以上流さないといけない」という制約を加えた問題を解く． もとの始点・終点とは別の始点・終点を新たに作り，下限のフローをその 2 つで請け負うようにすると，普通の最大流問題に帰着できる． 第 2 版 2 刷時点の蟻本の記述は間違っているので参考文献を見ること．
計算量
最大流アルゴリズムに依存．
使い方
g.add_edge(u, v, l, r)- u から v へ流量制約 [l, r] の辺を張る．
実装
//@require ./dinic-sparse.cc
template <class F>
struct maximum_flow_lr {
F flow;
int S, T;
flow_type sum_lb;
maximum_flow_lr() {}
maximum_flow_lr(int n) : flow(n + 2), S(n), T(n + 1), sum_lb(0) {}
void add_edge(int u, int v, int lb, int ub) {
assert(0 <= lb);
assert(lb <= ub);
if (u == v || ub == 0) return;
flow.add_edge(u, v, ub - lb);
// Three lines below should have no effect if lb == 0.
flow.add_edge(S, v, lb);
flow.add_edge(u, T, lb);
sum_lb += lb;
}
flow_type maximum_flow(int s, int t) {
int S = flow.n - 2, T = flow.n - 1;
flow_type a = flow.maximum_flow(S, T);
flow_type b = flow.maximum_flow(s, T);
flow_type c = flow.maximum_flow(S, t);
flow_type d = flow.maximum_flow(s, t);
return (a + c == sum_lb && a + b == sum_lb) ? b + d : -1;
}
};
using MF = maximum_flow_lr<dinic>;
検証
AOJ1615 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2447489#1