Adding amount of flow to capacity scaling algorithm.

1 files changed, 37 insertions, 31 deletions

diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp
index 2349ddd..cbf3b1b 100644
--- a/graph/capacityScaling.cpp
+++ b/graph/capacityScaling.cpp
@@ -1,35 +1,41 @@
-// Ford Fulkerson with capacity scaling.
-// Laufzeit: O(|E|^2 * log C)
-const int MAXN = 190000, MAXC = 1<<29;
-struct edge { int dest, capacity, rev; };
-vector<edge> adj[MAXN];
-int vis[MAXN], target, iter, cap;
+// Ford Fulkerson mit Capacity Scaling.
+// Laufzeit: O(|E|^2*log(C))
+struct MaxFlow { // Muss mit new erstellt werden!
+  static const int MAX_N = 500; // #Knoten, kein Einfluss auf die Laufzeit.
+  struct edge { int dest, rev; ll capacity, flow; };
+  vector<edge> adjlist[MAX_N];
+  int visited[MAX_N] = {0}, target, dfsCounter = 0;
+  ll capacity;
 
-void addedge(int x, int y, int c) {
-  adj[x].push_back(edge {y, c, (int)adj[y].size()});
-  adj[y].push_back(edge {x, 0, (int)adj[x].size() - 1});
-}
-
-bool dfs(int x) {
-  if (x == target) return 1;
-  if (vis[x] == iter) return 0;
-  vis[x] = iter;
-  for (edge& e: adj[x])
-    if (e.capacity >= cap && dfs(e.dest)) {
-      e.capacity -= cap;
-      adj[e.dest][e.rev].capacity += cap;
-      return 1;
+  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.capacity >= capacity && dfs(e.dest)) {
+        e.capacity -= capacity; adjlist[e.dest][e.rev].capacity += capacity;
+        e.flow += capacity; adjlist[e.dest][e.rev].flow -= capacity;
+        return 1;
+      }
     }
-  return 0;
-}
+    return 0;
+  }
 
-int maxflow(int S, int T) {
-  cap = MAXC, target = T;
-  int flow = 0;
-  while(cap) {
-    while(++iter, dfs(S))
-      flow += cap;
-    cap /= 2;
+  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});
+  }
+
+  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;
   }
-  return flow;
-}
\ No newline at end of file
+};