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 +++++++++++++++++++++++++++++++++++++++++++++++++
 graph/graph.tex        |   4 ++++
 math/math.tex          |   3 +++
 math/simpson.cpp       |  12 ++++++++++
 tcr.pdf                | Bin 305354 -> 309691 bytes
 5 files changed, 78 insertions(+)
 create mode 100644 graph/dinicScaling.cpp
 create mode 100644 math/simpson.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;
+  }
+}
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
diff --git a/math/math.tex b/math/math.tex
index 94adf9f..c2f5d63 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -109,6 +109,9 @@ Multipliziert Polynome $A$ und $B$.
 \end{itemize}
 \lstinputlisting{math/fft.cpp}
 
+\subsection{Numerisch Integrieren, Simpsonregel}
+\lstinputlisting{math/simpson.cpp}
+
 \subsection{3D-Kugeln}
 \lstinputlisting{math/spheres.cpp}
 
diff --git a/math/simpson.cpp b/math/simpson.cpp
new file mode 100644
index 0000000..dd887e2
--- /dev/null
+++ b/math/simpson.cpp
@@ -0,0 +1,12 @@
+double f(double x) { return x; }
+
+double simps(double a, double b) {
+  return (f(a) + 4.0 * f((a + b) / 2.0) + f(b)) * (b - a) / 6.0;
+}
+
+double integrate(double a, double b) {
+  double m = (a + b) / 2.0;
+  double l = simps(a, m), r = simps(m, b), tot = simps(a, b);
+  if (abs(l + r - tot) < EPSILON) return tot;
+  return integrate(a, m) + integrate(m, b);
+}
diff --git a/tcr.pdf b/tcr.pdf
index 8a3de2c..c188be3 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3