ホーム > libalgo

流量の下限制約付き最大流

概要

普通の最大流では 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

参考文献

最小流量制限付き最大流 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ