Network Flows

Maximum flow: the min-cut theorem, the Edmonds-Karp algorithm and applications to matchings.

A network is a directed graph where every edge has a capacity. The maximum flow is how much "fluid" can be pushed from the source s to the sink t. The fundamental theorem (Ford-Fulkerson): the maximum flow equals the minimum cut — the minimum total capacity of edges whose removal separates s from t. That is why flows solve both "how much can we push" and "what should we sever" problems. The Edmonds-Karp algorithm: while there is a path from s to t with positive residual capacities (found by BFS), push flow along it and update the RESIDUAL network: decrease forward edges, increase reverse ones. The reverse edges are the key: they let the algorithm "change its mind" and reroute flow already pushed.

Try it yourself — the code is editable

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const long long INF = 1e18;
int n, m;
std::vector<std::vector<long long>> cap;
std::vector<std::vector<int>> g;

long long bfs(int s, int t, std::vector<int> &parent) {
    std::fill(parent.begin(), parent.end(), -1);
    parent[s] = s;
    std::queue<std::pair<int, long long>> q;
    q.push({s, INF});

while (!q.empty()) {
        auto [v, flow] = q.front();
        q.pop();
        for (int to : g[v]) {
            if (parent[to] == -1 && cap[v][to] > 0) {
                parent[to] = v;
                long long nf = std::min(flow, cap[v][to]);
                if (to == t) return nf;
                q.push({to, nf});
            }
        }
    }
    return 0;
}

int main() {
    std::cin >> n >> m;
    cap.assign(n + 1, std::vector<long long>(n + 1, 0));
    g.assign(n + 1, {});

for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        if (cap[a][b] == 0 && cap[b][a] == 0) {
            g[a].push_back(b);
            g[b].push_back(a); // обратное ребро для остаточной сети
        }
        cap[a][b] += c;
    }

long long flow = 0, add;
    std::vector<int> parent(n + 1);
    while ((add = bfs(1, n, parent)) > 0) {
        flow += add;
        int v = n;
        while (v != 1) {
            int p = parent[v];
            cap[p][v] -= add;
            cap[v][p] += add;
            v = p;
        }
    }
    std::cout << "Максимальный поток: " << flow << "\n";
    return 0;
}

Input (sample — feel free to edit)

Edmonds-Karp, source 1, sink n. Enter: 4 5, then "a b capacity": 1 2 3, 1 3 2, 2 3 1, 2 4 2, 3 4 3

On the example the maximum flow is 5: 2 units along 1→2→4, 2 along 1→3→4 and 1 more along 1→2→3→4. Edmonds-Karp's complexity is O(V·E²); for dense problems there is the faster Dinic's algorithm. The main practical application is bipartite matching: the maximum number of "student-project" pairs where everyone is in at most one pair. Build a network: source → students (capacity 1) → admissible projects (capacity 1) → sink. Maximum flow = maximum matching.

Task: model on paper the problem "3 workers, 3 jobs, who can do what" as a network and run it through the program above (number them: 1 — the source, 2-4 — the workers, 5-7 — the jobs, 8 — the sink). Mark the lesson as completed.