Max Flow Lower Bound (graph/flow/maxflow-lower-bound.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 15:44:16+00:00
• Include: #include "graph/flow/maxflow-lower-bound.hpp"

各辺に容量の下限と上限があるフローネットワークを扱います。実行可能流の存在判定、および指定した始点から終点への最大流・最小流を求めることができます。

コンストラクタ

MaxFlowLowerBound<flow_t, F>(int V)

頂点数 V のフローネットワークを作成します。flow_t は流量の型、F は最大流アルゴリズムのクラステンプレートです。

制約

• $0 \leq V$
• F<flow_t> は add_edge、max_flow、INF、graph を持つ

計算量

• $O(V)$

add_edge

void add_edge(int from, int to, flow_t low, flow_t high)

頂点 from から to に、流量の下限が low、上限が high の有向辺を追加します。

制約

• $0 \leq \mathrm{from}, \mathrm{to} \lt V$
• $\mathrm{from} \neq \mathrm{to}$
• $0 \leq \mathrm{low} \leq \mathrm{high}$

計算量

• 償却 $O(1)$

can_flow

bool can_flow()

すべての辺の下限制約と上限制約、および各頂点での流量保存則を満たす実行可能流が存在する場合 true、存在しない場合 false を返します。

bool can_flow(int s, int t)

頂点 s を始点、頂点 t を終点とする実行可能流が存在する場合 true、存在しない場合 false を返します。

制約

• $0 \leq s, t \lt V$
• $s \neq t$
• 辺の追加後、can_flow、max_flow、min_flow のいずれも呼び出していない

計算量

• F による最大流計算1回分。変換後のグラフは頂点数 $V+2$、辺数は元の辺数から $O(V)$ 増加する

max_flow

optional<flow_t> max_flow(int s, int t)

すべての辺の下限制約と上限制約を満たす、頂点 s から t への最大流量を返します。実行可能流が存在しない場合は nullopt を返します。

制約

• $0 \leq s, t \lt V$
• $s \neq t$
• 辺の追加後、can_flow、max_flow、min_flow のいずれも呼び出していない

計算量

• F による最大流計算2回分。変換後のグラフは頂点数 $V+2$、辺数は元の辺数から $O(V)$ 増加する

min_flow

optional<flow_t> min_flow(int s, int t)

すべての辺の下限制約と上限制約を満たす、頂点 s から t への最小流量を返します。流量は頂点 s からの流出量と頂点 s への流入量の差として定義されるため、負になることがあります。実行可能流が存在しない場合は nullopt を返します。

制約

• $0 \leq s, t \lt V$
• $s \neq t$
• 辺の追加後、can_flow、max_flow、min_flow のいずれも呼び出していない

計算量

• F による最大流計算2回分。変換後のグラフは頂点数 $V+2$、辺数は元の辺数から $O(V)$ 増加する

output

void output(int M)

最初に追加した M 本の辺について、最後に求めた流量を追加順に1行ずつ出力します。

制約

• $0 \leq M \leq E$
• can_flow、max_flow、min_flow のいずれかを呼び出した後である

計算量

• $O(V + E)$

Verified with

• test/verify/aoj-1615.test.cpp

Code

#pragma once

#include <cassert>
#include <iostream>
#include <optional>
#include <vector>

template <typename flow_t, template <typename> class F>
struct MaxFlowLowerBound {
  F<flow_t> flow;
  std::vector<flow_t> in, up;
  int ts_edge, st_edge;
  int X, Y, V;
  flow_t sum;

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

  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);
    ts_edge = (int)flow.graph[t].size() - 1;
    st_edge = (int)flow.graph[s].size() - 1;
    return can_flow();
  }

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

  std::optional<flow_t> max_flow(int s, int t) {
    if (can_flow(s, t)) {
      return flow.max_flow(s, t);
    } else {
      return std::nullopt;
    }
  }

  std::optional<flow_t> min_flow(int s, int t) {
    if (can_flow(s, t)) {
      auto ret = flow.INF - flow.graph[t][ts_edge].cap;
      flow.graph[t][ts_edge].cap = flow.graph[s][st_edge].cap = 0;
      return ret - flow.max_flow(t, s);
    } else {
      return std::nullopt;
    }
  }

  void output(int M) {
    std::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) std::cout << p << std::endl;
  }
};

#line 2 "graph/flow/maxflow-lower-bound.hpp"

#include <cassert>
#include <iostream>
#include <optional>
#include <vector>

template <typename flow_t, template <typename> class F>
struct MaxFlowLowerBound {
  F<flow_t> flow;
  std::vector<flow_t> in, up;
  int ts_edge, st_edge;
  int X, Y, V;
  flow_t sum;

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

  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);
    ts_edge = (int)flow.graph[t].size() - 1;
    st_edge = (int)flow.graph[s].size() - 1;
    return can_flow();
  }

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

  std::optional<flow_t> max_flow(int s, int t) {
    if (can_flow(s, t)) {
      return flow.max_flow(s, t);
    } else {
      return std::nullopt;
    }
  }

  std::optional<flow_t> min_flow(int s, int t) {
    if (can_flow(s, t)) {
      auto ret = flow.INF - flow.graph[t][ts_edge].cap;
      flow.graph[t][ts_edge].cap = flow.graph[s][st_edge].cap = 0;
      return ret - flow.max_flow(t, s);
    } else {
      return std::nullopt;
    }
  }

  void output(int M) {
    std::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) std::cout << p << std::endl;
  }
};

Back to top page