Skip to content

Instantly share code, notes, and snippets.

@PanagiotisPtr
Last active April 28, 2021 23:24
Show Gist options
  • Save PanagiotisPtr/4793a17a3e238ca02c5b94326b5bd32d to your computer and use it in GitHub Desktop.
Save PanagiotisPtr/4793a17a3e238ca02c5b94326b5bd32d to your computer and use it in GitHub Desktop.
Simple implementation of the Dinic algorithm with Current Arc optimisation to find maximum flow
#include <limits>
#define min(a, b) a < b ? a : b
using namespace std;
// note - only works with positive flows
// for negative flows just add to make positive
template<typename lt = long, typename sz = size_t>
struct Dinic {
static constexpr lt INF = numeric_limits<lt>::max();
static constexpr lt MAX_EDGES = 1e7 + 5;
struct Edge {
sz next;
sz to;
lt flow;
};
sz N;
sz count;
sz* l; // levels
sz* curr; // current
sz* head; // head
sz* q; // queue
Edge* e; // edges
Dinic(sz maxEdges) {
N = maxEdges+1;
count = 1;
l = new sz[Dinic::MAX_EDGES];
curr = new sz[Dinic::MAX_EDGES];
head = new sz[Dinic::MAX_EDGES];
q = new sz[Dinic::MAX_EDGES];
e = new Edge[Dinic::MAX_EDGES];
}
~Dinic() {
delete l;
delete curr;
delete head;
delete q;
delete e;
}
inline void addDirect(sz from, sz to, sz cap) {
count++;
e[count].next = head[from];
e[count].to = to;
e[count].flow = cap;
head[from] = count;
}
inline void add(sz from, sz to, sz cap) {
addDirect(from, to, cap);
addDirect(to, from, 0);
}
lt dfs(sz s, sz t, lt lim = Dinic::INF) {
if (!lim || s == t) return lim;
lt flow = 0, f;
for (lt i = curr[s]; i; i = e[i].next) {
curr[s] = i;
if (l[e[i].to] == l[s] + 1 && (f = dfs(e[i].to, t, min(lim, e[i].flow)))) {
flow += f;
lim -= f;
e[i].flow -= f;
e[i^1].flow += f;
if (!lim) break;
}
}
return flow;
}
bool bfs(sz s, sz t) {
for (sz i = 0; i < N; i++) {
curr[i] = head[i];
l[i] = 0;
}
sz h=0;
q[h++] = s;
l[s] = 1;
while (h) {
lt tmp = q[--h];
for (sz i = head[tmp]; i; i = e[i].next) {
if (!l[e[i].to] && e[i].flow) {
l[e[i].to] = l[tmp] + 1;
q[h++] = e[i].to;
}
}
}
return l[t];
}
lt maxFlow(sz s, sz t) {
lt maxFlow = 0;
while (bfs(s, t)) {
maxFlow += dfs(s, t);
}
return maxFlow;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment