From 9e9c033aa41f786f494cadea43563f83f3e951a3 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 7 Sep 2024 23:41:49 +0200
Subject: insert divsum

---
 content/graph/dinicScaling.cpp | 21 +++++++++++++--------
 content/graph/graph.tex        |  4 ++--
 2 files changed, 15 insertions(+), 10 deletions(-)

(limited to 'content/graph')

diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp
index f4e833a..0974b78 100644
--- a/content/graph/dinicScaling.cpp
+++ b/content/graph/dinicScaling.cpp
@@ -26,17 +26,18 @@ bool bfs(ll lim) {
 	return dist[t] >= 0;
 }
 
-bool dfs(int v, ll flow) {
-	if (v == t) return true;
+ll dfs(int v, ll flow) {
+	if (v == t || flow == 0) return flow;
 	for (; pt[v] < sz(adj[v]); pt[v]++) {
 		Edge& e = adj[v][pt[v]];
 		if (dist[e.to] != dist[v] + 1) continue;
-		if (e.c - e.f >= flow && dfs(e.to, flow)) {
-			e.f += flow;
-			adj[e.to][e.rev].f -= flow;
-			return true;
+		ll cur = dfs(e.to, min(e.c - e.f, flow));
+		if (cur > 0) {
+			e.f += cur;
+			adj[e.to][e.rev].f -= cur;
+			return cur;
 	}}
-	return false;
+	return 0;
 }
 
 ll maxFlow(int source, int target) {
@@ -45,7 +46,11 @@ ll maxFlow(int source, int target) {
 	for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
 		while (bfs(lim)) {
 			pt.assign(sz(adj), 0);
-			while (dfs(s, lim)) flow += lim;
+			ll cur;
+			do {
+				cur = dfs(s, lim);
+				flow += cur;
+			} while (cur > 0);
 	}}
 	return flow;
 }
diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index 831f4e5..213c597 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -211,6 +211,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/minCostMaxFlow.cpp}
 \end{algorithm}
+\vfill\null
+\columnbreak
 
 \subsubsection{Dinic's Algorithm mit Capacity Scaling}
 \begin{methods}
@@ -218,8 +220,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
 \end{methods}
 \sourcecode{graph/dinicScaling.cpp}
-\vfill\null
-\columnbreak
 
 \optional{
 \subsubsection{Anwendungen}
-- 
cgit v1.2.3