From ca41d9ccd8ed00e9efa20bc104e21fc0e49a301d Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Mon, 19 Jun 2017 15:52:34 +0200
Subject: Adding Dinic's algorithm with capacity scaling and numerical
 integration with adaptive simpson rule.

---
 graph/dinicScaling.cpp | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)
 create mode 100644 graph/dinicScaling.cpp

(limited to 'graph/dinicScaling.cpp')

diff --git a/graph/dinicScaling.cpp b/graph/dinicScaling.cpp
new file mode 100644
index 0000000..0d188a8
--- /dev/null
+++ b/graph/dinicScaling.cpp
@@ -0,0 +1,59 @@
+const int INF = 0x3FFFFFFF, MAXN = 500;
+struct edge { int a, b; ll f, c; };
+int n, m, pt[MAXN], d[MAXN], s, t;
+vector<edge> e;
+vector<int> g[MAXN];
+ll flow = 0, lim;
+queue<int> q;
+
+void add_edge(int a, int b, ll c) {
+  g[a].push_back(e.size());
+  e.push_back(edge {a, b, 0, c});
+  g[b].push_back(e.size());
+  e.push_back(edge {b, a, 0, 0});
+}
+
+bool bfs() {
+  for (int i = 0; i < n; i++) d[i] = INF;
+  d[s] = 0; 
+  q.push(s);
+  while (!q.empty() && d[t] == INF) {
+    int cur = q.front(); q.pop();
+    for (int i = 0; i < (int)g[cur].size(); i++) {
+      int id = g[cur][i], to = e[id].b;
+      if (d[to] == INF && e[id].c - e[id].f >= lim) {
+        d[to] = d[cur] + 1;
+        q.push(to);
+      }
+    }
+  }
+  while (!q.empty()) q.pop();
+  return d[t] != INF;
+}
+
+bool dfs(int v, ll flow) {
+  if (flow == 0) return false;
+  if (v == t) return true;
+  for (; pt[v] < (int)g[v].size(); pt[v]++) {
+    int id = g[v][pt[v]], to = e[id].b;
+    if (d[to] == d[v] + 1 && e[id].c - e[id].f >= flow) {
+      int pushed = dfs(to, flow); 
+      if (pushed) {
+        e[id].f += flow;
+        e[id ^ 1].f -= flow;
+        return true;
+      }       
+    }
+  }
+  return false;
+}
+
+// Nicht vergessen, s und t zu setzen!
+void dinic() {
+  for (lim = (1LL << 62); lim >= 1;) {
+    if (!bfs()) { lim /= 2; continue; }
+    for (int i = 0; i < n; i++) pt[i] = 0;
+    int pushed;
+    while ((pushed = dfs(s, lim))) flow += lim;
+  }
+}
-- 
cgit v1.2.3