improved dinic, sped up hopcroft-karp

2 files changed, 50 insertions, 58 deletions

diff --git a/graph/dinicScaling.cpp b/graph/dinicScaling.cpp
index aecbddc..a795be1 100644
--- a/graph/dinicScaling.cpp
+++ b/graph/dinicScaling.cpp
@@ -1,63 +1,51 @@
-struct edge {
-	int from, to;
+struct Edge {
+	int to, rev;
 	ll f, c;
 };
 
-vector<edge> edges;
-vector<vector<int>> adjlist;
+vector<vector<Edge>> adj;
 int s, t;
 vector<int> pt, dist;
-ll flow, lim;
-queue<int> q;
 
-void addEdge(int from, int to, ll c) {
-	adjlist[from].push_back(sz(edges));
-	edges.push_back({from, to, 0, c});
-	adjlist[to].push_back(sz(edges));
-	edges.push_back({to, from, 0, 0});
+void addEdge(int u, int v, ll c) {
+	adj[u].push_back({v, (int)sz(adj[v]), 0, c});
+	adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0});
 }
 
-bool bfs() {
-	dist.assign(sz(dist), -1);
-	dist[t] = sz(adjlist) + 1;
-	q.push(t);
-	while (!q.empty() && dist[s] < 0) {
+bool bfs(ll lim) {
+	dist.assign(sz(adj), -1);
+	dist[s] = 0;
+	queue<int> q({s});
+	while (!q.empty() && dist[t] < 0) {
 		int cur = q.front(); q.pop();
-		for (int id : adjlist[cur]) {
-			int to = edges[id].to;
-			if (dist[to] < 0 &&
-			    edges[id ^ 1].c - edges[id ^ 1].f >= lim) {
-				dist[to] = dist[cur] - 1;
-				q.push(to);
+		for (Edge& e : adj[cur]) {
+			if (dist[e.to] < 0 && e.c - e.f >= lim) {
+				dist[e.to] = dist[cur] + 1;
+				q.push(e.to);
 	}}}
-	while (!q.empty()) q.pop();
-	return dist[s] >= 0;
+	return dist[t] >= 0;
 }
 
 bool dfs(int v, ll flow) {
-	if (flow == 0) return false;
 	if (v == t) return true;
-	for (; pt[v] < sz(adjlist[v]); pt[v]++) {
-		int id = adjlist[v][pt[v]], to = edges[id].to;
-		if (dist[to] == dist[v] + 1 &&
-		    edges[id].c - edges[id].f >= flow) {
-			if (dfs(to, flow)) {
-				edges[id].f += flow;
-				edges[id ^ 1].f -= flow;
-				return true;
-	}}}
+	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;
+	}}
 	return false;
 }
 
 ll maxFlow(int source, int target) {
-	s = source;
-	t = target;
-	flow = 0;
-	dist.resize(sz(adjlist));
-	for (lim = (1LL << 62); lim >= 1;) {
-		if (!bfs()) {lim /= 2; continue;}
-		pt.assign(sz(adjlist), 0);
-		while (dfs(s, lim)) flow += lim;
-	}
+	s = source, t = target;
+	ll flow = 0;
+	for (ll lim = (1LL << 62); lim >= 1; lim /= 2) {
+		while (bfs(lim)) {
+			pt.assign(sz(adj), 0);
+			while (dfs(s, lim)) flow += lim;
+	}}
 	return flow;
 }
diff --git a/graph/hopcroftKarp.cpp b/graph/hopcroftKarp.cpp
index 09d27bc..61ec469 100644
--- a/graph/hopcroftKarp.cpp
+++ b/graph/hopcroftKarp.cpp
@@ -1,43 +1,47 @@
-vector<vector<int>> adjlist;
+vector<vector<int>> adj;
 // pairs ist der gematchte Knoten oder -1
-vector<int> pairs, dist;
+vector<int> pairs, dist, ptr;
 
-bool bfs(int n) {
+bool bfs(int l) {
 	queue<int> q;
-	for(int i = 0; i < n; i++) {
+	for(int i = 0; i < l; i++) {
 		if (pairs[i] < 0) {dist[i] = 0; q.push(i);}
 		else dist[i] = -1;
 	}
+	bool exist = false;
 	while(!q.empty()) {
 		int u = q.front(); q.pop();
-		for (int v : adjlist[u]) {
-			if (pairs[v] < 0) return true;
+		for (int v : adj[u]) {
+			if (pairs[v] < 0) {exist = true; continue;}
 			if (dist[pairs[v]] < 0) {
 				dist[pairs[v]] = dist[u] + 1;
 				q.push(pairs[v]);
 	}}}
-	return false;
+	return exist;
 }
 
 bool dfs(int u) {
-	for (int v : adjlist[u]) {
+	for (; ptr[u] < sz(adj[u]); ptr[u]++) {
+		int v = adj[u][ptr[u]];
 		if (pairs[v] < 0 ||
 		   (dist[pairs[v]] > dist[u] && dfs(pairs[v]))) {
 			pairs[v] = u; pairs[u] = v;
 			return true;
 	}}
-	dist[u] = -1;
 	return false;
 }
 
-int hopcroft_karp(int n) { // n = #Knoten links
+int hopcroft_karp(int l) { // l = #Knoten links
 	int ans = 0;
-	pairs.assign(sz(adjlist), -1);
-	dist.resize(n);
+	pairs.assign(sz(adj), -1);
+	dist.resize(l);
 	// Greedy Matching, optionale Beschleunigung.
-	for (int i = 0; i < n; i++) for (int w : adjlist[i])
+	for (int i = 0; i < l; i++) for (int w : adj[i])
 		if (pairs[w] < 0) {pairs[i] = w; pairs[w] = i; ans++; break;}
-	while(bfs(n)) for(int i = 0; i < n; i++)
-		if (pairs[i] < 0) ans += dfs(i);
+	while(bfs(l)) {
+		ptr.assign(l, 0);
+		for(int i = 0; i < l; i++) {
+			if (pairs[i] < 0) ans += dfs(i);
+	}}
 	return ans;
 }