graph.maxflow

graph.maxflow.cc

struct MaxFlow {
  int n;
  vvi d, c;
  vector<int> level, iter;
  int flow;

  MaxFlow(vvi& _d, vvi& _c, int s, int t) {
    d = _d; c = _c;
    n = _d.size();
    level.resize(n);
    iter.resize(n);
    int cur_flow = 0;
    loop {
      bfs(s);
      if (level[t] < 0) { flow = cur_flow; return; }
      rep (i, n) iter[i] = 0;
      for (int f = 0;;) {
        f = dfs(s, t, inf);
        if (f <= 0) break;
        cur_flow += f;
      }
    }
  }

  int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int i = iter[v]; i < d[v].size(); ++i) {
      int u = d[v][i]; // v -> u
      if (c[v][u] > 0 and level[v] < level[u]) {
        int d = dfs(u, t, min(f, c[v][u]));
        if (d > 0) {
          c[v][u] -= d;
          c[u][v] += d;
          return d;
        }
      }
    }
    return 0;
  }

  void bfs(int s) {
    rep (i, n) level[i] = i == s ? 0 : -1;
    queue<int> q; q.push(s);
    while (not q.empty()) {
      int u = q.front(); q.pop();
      for (auto&v: d[u]) { // u -> v
        if (c[u][v] > 0 and level[v] < 0) {
          level[v] = level[u] + 1;
          q.push(v);
        }
      }
    }
  }
};

Example

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout.setf(ios::fixed);
  cout.precision(10);

  stringstream input(
"  7"
"  0 6"
"  1 2"
"  1 4"
"  3 2"
"  5 2"
"  5 4"
"  0 1"
"  0 3"
"  0 5"
"  2 6"
"  4 6");
  int answer = 2;

  {
    int n; input >> n;
    int s, t; input >> s >> t;
    vvi d(n, vi(n));
    vvi c(n, vi(n, 0));
    loop {
      int a, b; input >> a >> b;
      if (not input) break;
      d[a].push_back(b);
      c[a][b] = 1;
    }
    MaxFlow mf(d, c, s, t);
    cout << mf.flow << endl;
    assert(mf.flow == answer);
  }

  stringstream input2(
"  6"
"  0 5"
"  0 1 3"
"  0 2 3"
"  1 2 2"
"  1 3 3"
"  2 4 2"
"  3 4 4"
"  3 5 2"
"  4 5 3");
  int answer2 = 5;
  {
    int n; input2 >> n;
    int s, t; input2 >> s >> t;
    vvi neighbor_list(n, vi(n));
    vvi capacity_table(n, vi(n, 0));
    loop {
      int a, b, c; input2 >> a >> b >> c;
      if (not input2) break;
      neighbor_list[a].push_back(b);
      capacity_table[a][b] = c;
    }
    MaxFlow mf(neighbor_list, capacity_table, s, t);
    cout << mf.flow << endl;
    assert(mf.flow == answer2);
  }
      

  return 0;
}