1 files changed, 31 insertions, 43 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;
 }