From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 graph/capacityScaling.cpp | 65 +++++++++++++++++++++++++++--------------------
 1 file changed, 37 insertions(+), 28 deletions(-)

(limited to 'graph/capacityScaling.cpp')

diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp
index 8571e2b..b59c322 100644
--- a/graph/capacityScaling.cpp
+++ b/graph/capacityScaling.cpp
@@ -1,35 +1,44 @@
-// Ford Fulkerson mit Capacity Scaling. Laufzeit: O(|E|^2*log(C))
-static const int MAX_N = 500; // #Knoten, egal für die Laufzeit.
-struct edge { int dest, rev; ll cap, flow; };
-vector<edge> adjlist[MAX_N];
-int visited[MAX_N], target, dfsCounter;
+struct edge {
+	int from, to; 
+	ll f, c;
+};
+
+vector<edge> edges;
+vector<vector<int>> adjlist;
+int s, t, dfsCounter;
+vector<int> visited;
 ll capacity;
 
-bool dfs(int x) {
-  if (x == target) return 1;
-  if (visited[x] == dfsCounter) return 0;
-  visited[x] = dfsCounter;
-  for (edge &e : adjlist[x]) {
-    if (e.cap >= capacity && dfs(e.dest)) {
-      e.cap -= capacity; adjlist[e.dest][e.rev].cap += capacity;
-      e.flow += capacity; adjlist[e.dest][e.rev].flow -= capacity;
-      return 1;
-  }}
-  return 0;
+void addEdge(int from, int to, ll c) {
+	adjlist[from].push_back(edges.size());
+	edges.push_back({from, to, 0, c});
+	adjlist[to].push_back(edges.size());
+	edges.push_back({to, from, 0, 0});
 }
 
-void addEdge(int u, int v, ll c) {
-  adjlist[u].push_back(edge {v, (int)adjlist[v].size(), c, 0});
-  adjlist[v].push_back(edge {u, (int)adjlist[u].size() - 1, 0, 0});
+bool dfs(int x) {
+	if (x == t) return true;
+	if (visited[x] == dfsCounter) return false;
+	visited[x] = dfsCounter;
+	for (int id : adjlist[x]) {
+		if (edges[id].c >= capacity && dfs(edges[id].to)) {
+			edges[id].c -= capacity; edges[id ^ 1].c += capacity;
+			edges[id].f += capacity; edges[id ^ 1].f -= capacity;
+			return true;
+	}}
+	return false;
 }
 
-ll maxFlow(int s, int t) {
-  capacity = 1L << 62;
-  target = t;
-  ll flow = 0L;
-  while (capacity) {
-    while (dfsCounter++, dfs(s)) flow += capacity;
-    capacity /= 2;
-  }
-  return flow;
+ll maxFlow(int source, int target) {
+	capacity = 1ll << 62;
+	s = source;
+	t = target;
+	ll flow = 0;
+	visited.assign(adjlist.size(), 0);
+	dfsCounter = 0;
+	while (capacity) {
+		while (dfsCounter++, dfs(s)) flow += capacity;
+		capacity /= 2;
+	}
+	return flow;
 }
-- 
cgit v1.2.3