tests/aoj/edmonds_karp.maximum_flow.test.cpp

View this file on GitHub
Last update: 2021-06-13 17:53:40+02:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"

#include "../../code/graphs/edmondsKarp.cc"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int V, E;
  cin >> V >> E;

  EK ek(V, 0, V - 1);

  F0R(i, E) {
      int u, v, c;
      cin >> u >> v >> c;
      ek.add(u, v, c);
  }

  cout << ek.maxflow() << endl;
}

#line 1 "tests/aoj/edmonds_karp.maximum_flow.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"

#line 1 "code/graphs/edmondsKarp.cc"

#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/graphs/flowedge.cc"
template <typename F>
struct edge {
  edge(int from, int to, F capacity, F flow = 0)
      : mfrom(from), mto(to), mcapacity(capacity), mflow(flow) {}
  int mfrom, mto;
  F mcapacity, mflow;
  int other(int v) { return v == mfrom ? mto : mfrom; }
  F capacity(int v) { return v == mfrom ? mcapacity : 0; }
  F flow(int v) { return v == mfrom ? mflow : -mflow; }
  void adjust(int v, F amount) {
    mflow += v == mfrom ? amount : -amount;
  }
};
template <typename F>
ostream& operator<<(ostream& o, const edge<F>& e) {
  return o << e.mfrom << "-- " << e.mflow << '/'
           << e.mcapacity << " -->" << e.mto;
}
#line 3 "code/graphs/edmondsKarp.cc"
template <typename F = ll>
struct EK {
  vvi adj;
  vector<edge<F>> edges;
  int S, T;
  EK(int n, int s = -1, int t = -1) { reset(n, s, t); }
  int add(int from, int to, F c = numeric_limits<F>::max(), F f = 0) {
    edges.eb(from, to, c, f);
    adj[from].pb(SZ(edges) - 1);
    adj[to].pb(SZ(edges) - 1);
    return SZ(edges) - 1;
  }
  void clear() { edges.clear(); adj.clear(); }
  void reset(int n, int s = -1, int t = -1) {
    clear();
    adj.resize(n + (s == -1) + (t == -1));
    S = s == -1 ? n : s;
    T = t == -1 ? n + (s == -1) : t;
  }
  F augment(int s, int t) {
    vii p(SZ(adj), {-1, -1});
    queue<int> q;
    p[s] = mp(-1, 0);
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      if (v == t) break;
      q.pop();
      for (int i : adj[v]) {
        auto& e = edges[i];
        if (p[e.other(v)].se == -1 && e.flow(v) < e.capacity(v)) {
          p[e.other(v)] = mp(v, i); q.push(e.other(v));
        }
      }
    }
    if (p[t].se == -1) return 0;
    F mf = numeric_limits<F>::max();
    for (ii c = p[t]; c.fi != -1; c = p[c.fi])
      ckmin(mf, edges[c.se].capacity(c.fi) - edges[c.se].flow(c.fi));
    for (ii c = p[t]; c.fi != -1; c = p[c.fi])
      edges[c.se].adjust(c.fi, mf);
    return mf;
  }
  F maxflow() { return maxflow(S, T); }
  F maxflow(int s, int t) {
    F maxflow = 0;
    while (F plus = augment(s, t)) maxflow += plus;
    return maxflow;
  }
};

#line 4 "tests/aoj/edmonds_karp.maximum_flow.test.cpp"

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  int V, E;
  cin >> V >> E;

  EK ek(V, 0, V - 1);

  F0R(i, E) {
      int u, v, c;
      cin >> u >> v >> c;
      ek.add(u, v, c);
  }

  cout << ek.maxflow() << endl;
}