There is one problem of which I am very much fond of which is ” The Max Flow Problem”. I’ve struggled a lot in understanding this but finally I came up with a solution worth sharing and describing my approach to the problem.
The maximum flow problem was first formulated in 1954 by T.E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow.
The problem can be understood as follows –
“Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.“
So, what are we being asked for in this max-flow problem?
We are given a network – a directed graph, in which every edge has a certain capacity c associated with it, a starting vertex (the source, X in the example above), and an ending vertex (the sink). We are asked to associate another value f satisfying f <= c, for each edge such that for every vertex other than the source and the sink, the sum of the values associated to the edges that enter it must equal the sum of the values associated to the edges that leave it. We will call f the flow along that edge. Furthermore, we are asked to maximize the sum of the values associated with the arcs leaving the source, which is the total flow in the network.
The image below shows the optimal solution to an instance of this problem, each edge is labelled with the values f/c associated with it.
How to Solve It?
First, let us define two basic concepts for understanding flow networks: residual networks and augmenting paths. Consider an arbitrary flow in a network. The residual network has the same vertices as the original network and one or two edges for each edge in the original. More specifically, if the flow along the edge x-y is less than the capacity there is a forward edge x-y with a capacity equal to the difference between the capacity and the flow (this is called the residual capacity), and if the flow is positive there is a backward edge y-x with a capacity equal to the flow on x-y. An augmenting path is simply a path from the source to the sink in the residual network, whose purpose is to increase the flow in the original one. It is important to understand that the edges in this path can point the “wrong way” according to the original network. The path capacity of a path is the minimum capacity of an edge along that path.
To solve max-flow problems we can use the following algorithm: start with no flow everywhere and increase the total flow in the network while there is an augmenting path from the source to the sink with no full forward edges or empty backward edges – a path in the residual network.
Code :
| template <int MAXV, class T = int> | |
| struct Dinic | |
| { | |
| const static bool SCALING = false; // non-scaling = V^2E, Scaling=VElog(U) with higher constant | |
| int lim = 1; | |
| const T INF = numeric_limits<T>::max(); | |
| struct edge | |
| { | |
| int to, rev; | |
| T cap, flow; | |
| }; | |
| int s = MAXV - 2, t = MAXV - 1; | |
| int level[MAXV], ptr[MAXV]; | |
| vector<edge> adj[MAXV]; | |
| void addEdge(int a, int b, T cap, bool isDirected = true) | |
| { | |
| adj[a].push_back({b, (int)adj[b].size(), cap, 0}); | |
| adj[b].push_back({a, (int)adj[a].size() - 1, isDirected ? 0 : cap, 0}); | |
| } | |
| bool bfs() | |
| { | |
| queue<int> q({s}); | |
| fill(level, level + MAXV, -1); | |
| level[s] = 0; | |
| while (!q.empty() && level[t] == -1) | |
| { | |
| int v = q.front(); | |
| q.pop(); | |
| for (auto e : adj[v]) | |
| { | |
| if (level[e.to] == -1 && e.flow < e.cap && (!SCALING || e.cap - e.flow >= lim)) | |
| { | |
| q.push(e.to); | |
| level[e.to] = level[v] + 1; | |
| } | |
| } | |
| } | |
| return level[t] != -1; | |
| } | |
| T dfs(int v, T flow) | |
| { | |
| if (v == t || !flow) | |
| return flow; | |
| for (; ptr[v] < adj[v].size(); ptr[v]++) | |
| { | |
| edge &e = adj[v][ptr[v]]; | |
| if (level[e.to] != level[v] + 1) | |
| continue; | |
| if (T pushed = dfs(e.to, min(flow, e.cap - e.flow))) | |
| { | |
| e.flow += pushed; | |
| adj[e.to][e.rev].flow -= pushed; | |
| return pushed; | |
| } | |
| } | |
| return 0; | |
| } | |
| long long calc() | |
| { | |
| long long flow = 0; | |
| for (lim = SCALING ? (1 << 30) : 1; lim > 0; lim >>= 1) | |
| { | |
| while (bfs()) | |
| { | |
| fill(ptr, ptr + MAXV, 0); | |
| while (T pushed = dfs(s, INF)) | |
| flow += pushed; | |
| } | |
| } | |
| return flow; | |
| } | |
| }; |
Applications of this Problem :
- Multi-source multi-sink maximum flow problem
- Minimum path cover in directed acyclic graph
- Maximum cardinality bipartite matching
- Maximum flow with vertex capacities
- Maximum number of paths from s to t
- Closure problem
Real World Applications
- Airline scheduling
- Baseball elimination
- Circulation–demand problem
- Image segmentation
Ciaó
Cogitare Et Credere
Co-Authored by-
Subhash Suman
B.Tech IIT Mandi
Codeforces – Candidate Master
TᗯIᑎ ᖇEᗩᒪITY 