code/graphs/flowedge.cc

• View this file on GitHub
• Last update: 2021-06-13 17:53:40+02:00

Depends on

• code/template.cc

Required by

• code/graphs/dinic.cc
• code/graphs/edmondsKarp.cc
• code/graphs/pushRelabel.cc

Verified with

• tests/aoj/dinic.maximum_flow.test.cpp
• tests/aoj/edmonds_karp.maximum_flow.test.cpp
• tests/aoj/push_relabel.maximum_flow.test.cpp
• tests/yosupo/dinic.bipartitematching.test.cpp

Code

#include "../template.hh"
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 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;
}

Back to top page