1 files changed, 52 insertions, 50 deletions
diff --git a/graph/dinicScaling.cpp b/graph/dinicScaling.cpp
index ebbcc27..1b58d29 100644
--- a/graph/dinicScaling.cpp
+++ b/graph/dinicScaling.cpp
@@ -1,61 +1,63 @@
-// Laufzeit: O(|V|^2*|E|)
-// Knoten müssen von 0 nummeriert sein.
-const int INF = 0x3FFFFFFF, MAXN = 500;
-struct edge { int a, b; ll f, c; };
-int n, m, pt[MAXN], d[MAXN], s, t;
-vector<edge> e;
-vector<int> g[MAXN];
-ll flow = 0, lim;
+struct edge {
+	int from, to; 
+	ll f, c;
+};
+
+vector<edge> edges;
+vector<vector<int>> adjlist;
+int s, t;
+vector<int> pt, dist;
+ll flow, lim;
 queue<int> q;
 
-void addEdge(int a, int b, ll c) {
-  g[a].push_back(e.size());
-  e.push_back(edge {a, b, 0, c});
-  g[b].push_back(e.size());
-  e.push_back(edge {b, a, 0, 0});
+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});
 }
 
 bool bfs() {
-  for (int i = 0; i < n; i++) d[i] = INF;
-  d[s] = 0; 
-  q.push(s);
-  while (!q.empty() && d[t] == INF) {
-    int cur = q.front(); q.pop();
-    for (int i = 0; i < (int)g[cur].size(); i++) {
-      int id = g[cur][i], to = e[id].b;
-      if (d[to] == INF && e[id].c - e[id].f >= lim) {
-        d[to] = d[cur] + 1;
-        q.push(to);
-      }
-    }
-  }
-  while (!q.empty()) q.pop();
-  return d[t] != INF;
+	dist.assign(sz(dist), -1);
+	dist[t] = sz(adjlist) + 1; 
+	q.push(t);
+	while (!q.empty() && dist[s] < 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);
+	}}}
+	while (!q.empty()) q.pop();
+	return dist[s] >= 0;
 }
 
 bool dfs(int v, ll flow) {
-  if (flow == 0) return false;
-  if (v == t) return true;
-  for (; pt[v] < (int)g[v].size(); pt[v]++) {
-    int id = g[v][pt[v]], to = e[id].b;
-    if (d[to] == d[v] + 1 && e[id].c - e[id].f >= flow) {
-      int pushed = dfs(to, flow); 
-      if (pushed) {
-        e[id].f += flow;
-        e[id ^ 1].f -= flow;
-        return true;
-      }       
-    }
-  }
-  return false;
+	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;
+	}}}
+	return false;
 }
 
-// Nicht vergessen, s und t zu setzen!
-void dinic() {
-  for (lim = (1LL << 62); lim >= 1;) {
-    if (!bfs()) { lim /= 2; continue; }
-    for (int i = 0; i < n; i++) pt[i] = 0;
-    int pushed;
-    while ((pushed = dfs(s, lim))) flow += lim;
-  }
+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;
+	}
+	return flow;
 }