Adding Dinic's algorithm with capacity scaling and numerical integration with adaptive simpson rule.

2 files changed, 63 insertions, 0 deletions

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;
+  }
+}
diff --git a/graph/graph.tex b/graph/graph.tex
index 3870dc3..7f884fe 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -73,6 +73,10 @@ Gut bei dünn besetzten Graphen.
 Gut bei sehr dicht besetzten Graphen.
 \lstinputlisting{graph/pushRelabel.cpp}
 
+\subsubsection{Dinic's Algorithm mit Capacity Scaling}
+Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling.
+\lstinputlisting{graph/dinicScaling.cpp}
+
 \subsubsection{Anwendungen}
 \begin{itemize}[nosep]
 	\item \textbf{Maximum Edge Disjoint Paths}\newline