From 5de23397c83bb57067fbc1286d46f13cfa7a4de9 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 6 Oct 2016 22:22:53 +0200 Subject: Cosmetic changes to Ford Fulkerson with capacity scaling. --- graph/capacityScaling.cpp | 18 +++++++----------- 1 file changed, 7 insertions(+), 11 deletions(-) (limited to 'graph') diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp index cbf3b1b..11c643f 100644 --- a/graph/capacityScaling.cpp +++ b/graph/capacityScaling.cpp @@ -1,8 +1,7 @@ -// Ford Fulkerson mit Capacity Scaling. -// Laufzeit: O(|E|^2*log(C)) +// 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; }; + static const int MAX_N = 500; // #Knoten, egal für die Laufzeit. + struct edge { int dest, rev; ll cap, flow; }; vector adjlist[MAX_N]; int visited[MAX_N] = {0}, target, dfsCounter = 0; ll capacity; @@ -12,12 +11,11 @@ struct MaxFlow { // Muss mit new erstellt werden! 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; + 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; } @@ -31,9 +29,7 @@ struct MaxFlow { // Muss mit new erstellt werden! target = t; ll flow = 0L; while (capacity) { - while (dfsCounter++, dfs(s)) { - flow += capacity; - } + while (dfsCounter++, dfs(s)) flow += capacity; capacity /= 2; } return flow; -- cgit v1.2.3