最小流量制限付き最大流

説明

流量の下限と上限が決まっているときの最大流。

計算量

• うく

実装例

• MaxFlowLowerBound($V$):= 頂点数 $V$ で初期化する。
• add_edge($from$, $to$, $low$, $high$):= 頂点 $from$ から $to$ に容量 $[low, high]$ の辺を張る。
• max_flow($s$, $t$):= 頂点 $s$ から $t$ に最大流を流し、その流量を返す。流せなかったとき $-1$。
• can_flow($s$, $t$):= 頂点 $s$ から $t$ に制約を満たせるように流せるか判定する。
• can_flow():= グラフに制約を満たす循環フロー(すべての点での流出量が流入量と等しい流れ)を流せるか判定する。
• min_flow($s$, $t$):= 頂点 $s$ から $t$ に最小流(制約を満たすもののうち最小の流量）を流し、その流量を返す。流せなかったとき $-1$。
• output($m$):= 流したフローを出力する。

template< typename flow_t, template< typename > class F >
struct MaxFlowLowerBound {
  F< flow_t > flow;
  vector< flow_t > in, up;
  typename F< flow_t >::edge *latte, *malta;
  int X, Y, V;
  flow_t sum;

  MaxFlowLowerBound(int V) : V(V), flow(V + 2), X(V), Y(V + 1), sum(0), in(V) {}

  void add_edge(int from, int to, flow_t low, flow_t high) {
    assert(from != to);
    flow.add_edge(from, to, high - low, up.size());
    in[from] -= low;
    in[to] += low;
    up.emplace_back(high);
  }

  void build() {
    for(int i = 0; i < V; i++) {
      if(in[i] > 0) {
        flow.add_edge(X, i, in[i]);
        sum += in[i];
      } else if(in[i] < 0) {
        flow.add_edge(i, Y, -in[i]);
      }
    }
  }

  bool can_flow(int s, int t) {
    assert(s != t);
    flow.add_edge(t, s, flow.INF);
    latte = &flow.graph[t].back();
    malta = &flow.graph[s].back();
    return can_flow();
  }

  bool can_flow() {
    build();
    auto ret = flow.max_flow(X, Y);
    return ret >= sum;
  }

  flow_t max_flow(int s, int t) {
    if(can_flow(s, t)) {
      return flow.max_flow(s, t);
    } else {
      return -1;
    }
  }

  flow_t min_flow(int s, int t) {
    if(can_flow(s, t)) {
      auto ret = flow.INF - latte->cap;
      latte->cap = malta->cap = 0;
      return ret - flow.max_flow(t, s);
    } else {
      return -1;
    }
  }

  void output(int M) {
    vector< flow_t > ans(M);
    for(int i = 0; i < flow.graph.size(); i++) {
      for(auto &e : flow.graph[i]) {
        if(!e.isrev && ~e.idx) ans[e.idx] = up[e.idx] - e.cap;
      }
    }
    for(auto &p : ans) cout << p << endl;
  }
};

検証

AOJ1615 プレゼント交換会

int main() {
  int N, M;
  while(cin >> N >> M, N) {
    vector< int > U(M), V(M);
    for(int i = 0; i < M; i++) {
      cin >> U[i] >> V[i];
      --U[i], --V[i];
    }
    auto check = [&](int low, int high) {
      MaxFlowLowerBound< int, Dinic > flow(N + M + 2);
      int S = N + M, T = N + M + 1;
      for(int i = 0; i < M; i++) {
        flow.add_edge(S, i, 1, 1);
        flow.add_edge(i, M + U[i], 0, 1);
        flow.add_edge(i, M + V[i], 0, 1);
      }
      for(int i = 0; i < N; i++) {
        flow.add_edge(M + i, T, low, high);
      }
      return flow.max_flow(S, T) == M;
    };

    int p = 0, q = N;
    int l = 0;
    for(int r = 0; r <= N; r++) {
      while(l <= r && check(l, r)) {
        p = l, q = r;
        ++l;
      }
    }
    cout << p << " " << q << endl;
  }
}

参考

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