# Dinitz reference implementation

a guest
Jul 17th, 2022
1,064
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <tuple>
5.
6. using namespace std;
7.
8. typedef long long ll;
9.
10. const ll INF = 1e18 + 1000;
11.
12. // A reference implementation of Dinitz's algorithm
13. // Note: this implementation has been created with educational
14. // value in mind, not efficiency. Other implementations with
15. // better constant factors exist; if you're looking for a black
16. // box to use in a contest, you're better off looking elsewhere.
17. // See more: https://codeforces.com/blog/entry/104960
18.
19. // This struct represents the state of an edge, together with its
20. // reverse edge that may appear in some G_f, during the execution
21. // of the algorithm.
22. struct Edge {
23.   int from, to; // The edge is from->to in the original graph.
24.   ll capac, flow;
25.
26.   // Gets the endpoint other than u of the edge.
27.   int oth (int u) {
28.     return u ^ from ^ to; // xor trick
29.   }
30.
31.   // Gets the capacity of the edge u->oth(u) in G_f.
32.   ll capacity (int u) {
33.     if (u == from) {
34.       return capac - flow;
35.     } else {
36.       return flow;
37.     }
38.   }
39.
40.   // Returns whether the edge u->oth(u) exists in u.
41.   bool exists (int u) {
42.     return capacity(u) != 0;
43.   }
44.
45.   // Adds df flow to the edge in G if u == from,
46.   // subtracts it otherwise.
47.   void add_flow (int u, ll df) {
48.     if (u == from) {
49.       flow += df;
50.     } else {
51.       flow -= df;
52.     }
53.   }
54. };
55.
56. // At any given time, represents one particular G_f. We modify this class on the
57. // fly when adding a flow.
58. class MaxFlow {
59.   // number of vertices
60.   int n;
61.   int source, sink;
62.
63.   // adj[u] is the set of edges incident to u
65.
66.   // we also keep a list of all edges, for easy retrieval of flow on edge
67.   vector<Edge*> edges;
68.
69.   // lvl[u] is the layer (or distance from s) at the current DAG.
70.   // updated via dinitz_bfs
71.   vector<int> lvl;
72.
73.   void dinitz_bfs () {
74.     // we use a value greater than n to denote "unexplored"
75.     // or what is called "undefined" in the blog. no vertex actually
76.     // has a distance greater than n.
77.     lvl = vector<int> (n, n + 10);
78.
79.     queue<int> Q;
80.     Q.push(source);
81.     lvl[source] = 0;
82.
83.     while (!Q.empty()) {
84.       int u = Q.front();
85.       Q.pop();
86.
87.       for (auto e : adj[u]) {
88.         if (!e->exists(u)) {
89.           continue;
90.         }
91.
92.         int v = e->oth(u);
93.         if (lvl[v] > n) {
94.           lvl[v] = lvl[u] + 1;
95.           Q.push(v);
96.         }
97.
98.         // in the actual implementation, we don't explicitly add edges to the
99.         // DAG. we simply say that an edge u->v is in the DAG if lvl[v] = lvl[u] + 1
100.       }
101.     }
102.   }
103.
104.   bool in_current_dag (int u, int v) {
105.     return lvl[v] == lvl[u] + 1;
106.   }
107.
108.   // as in the blog, tries to push F flow from u
109.   // returns how much flow could actually be pushed
110.   // the third parameter is used to maintain what is
111.   // called v.blocked in the blog; note that it is a
112.   // reference.
113.   ll dinitz_dfs (int u, ll F, vector<int> &blocked) {
114.     if (u == sink) {
115.       return F;
116.     }
117.
118.     ll flow_pushed = 0;
119.     bool all_blocked = true;
120.     for (auto e : adj[u]) {
121.       int v = e->oth(u);
122.       if (!in_current_dag(u, v)) {
123.         continue;
124.       }
125.
126.       if (e->exists(u) && !blocked[v]) {
127.         // note that here we use e->capacity(u) instead of
128.         // the e.capacity - e.flow in the blog, as the Edge
129.         // struct automatically modifies the capacities when
131.         ll dF = dinitz_dfs(v, min(F, e->capacity(u)), blocked);
132.
133.         flow_pushed += dF;
134.         F -= dF;
136.       }
137.
138.       if (e->exists(u) && !blocked[v]) {
139.         all_blocked = false;
140.       }
141.     }
142.
143.     if (all_blocked) {
144.       blocked[u] = true;
145.     }
146.
147.     return flow_pushed;
148.   }
149.
150.   void dinitz_dfs () {
151.     vector<int> blocked (n, false);
152.     dinitz_dfs(source, INF, blocked);
153.   }
154.
155. public:
156.   MaxFlow (int _source, int _sink, const vector<tuple<int, int, ll>> &_edges)
157.     : source(_source), sink(_sink) {
158.     n = max(1 + source, 1 + sink);
159.     for (auto e : _edges) {
160.       n = max(n, max(1 + get<0>(e), 1 + get<1>(e)));
161.     }
162.
163.     adj = vector<vector<Edge*>> (n, vector<Edge*> (0));
164.     for (auto e : _edges) {
165.       auto ee = new Edge();
166.       ee->from = get<0>(e);
167.       ee->to = get<1>(e);
168.       ee->flow = 0;
169.       ee->capac = get<2>(e);
170.
171.       edges.push_back(ee);
172.       if (ee->from != ee->to) {
173.         // don't add self-loops to the adjacency list; they don't do anything
174.         // useful to the graph and may mess up the algorithm.
177.       }
178.     }
179.   }
180.
181.   ll calc_max_flow () {
182.     while (true) {
183.       dinitz_bfs();
184.       if (lvl[sink] > n) {
185.         // t is not reachable from s anymore.
186.         break;
187.       }
188.       dinitz_dfs();
189.     }
190.
191.     ll ans = 0;
192.     for (auto e : adj[source]) {
193.       if (e->from == source) {
194.         ans += e->flow;
195.       } else {
196.         ans -= e->flow;
197.       }
198.     }
199.
200.     return ans;
201.   }
202.
203.   ll flow_on_edge (int idx) {
204.     return edges[idx]->flow;
205.   }
206. };
207.
208. // convenience class for building the graph without awkward make_tuples
209. class GraphBuilder {
210.   int source, sink;
211.   vector<tuple<int, int, ll>> edges;
212.
213. public:
214.   GraphBuilder (int _source, int _sink) : source(_source), sink(_sink), edges(0) {}
215.
216.   void add_edge (int u, int v, ll capacity) {
217.     edges.push_back(make_tuple(u, v, capacity));
218.   }
219.
220.   MaxFlow build () {
221.     return MaxFlow(source, sink, edges);
222.   }
223. };
224.
225. int main () {
226.   ios::sync_with_stdio(false);
227.   cin.tie(0);
228.
229.   int n, m;
230.   cin >> n >> m;
231.
232.   GraphBuilder gb (1, n);
233.   for (int i = 0; i < m; i++) {
234.     int u, v;
235.     ll capac;
236.     cin >> u >> v >> capac;
237.