A flow network is a directed graph with capacities. A flow assigns each edge a value ≤ capacity, conserves at every vertex except source s and sink t. Max flow is the maximum net leaving s.
Min cut: a partition (S, T) with s∈S, t∈T; capacity is the sum of edges S→T. The theorem: max flow = min cut. That is why 'minimum edges to disconnect' and 'maximum assignments' share a template.
CSES Download Speed (max flow), Police Chase (min cut), School Dance (bipartite matching = flow). Rare on CF Div. 2; expected in OI. Dinic is the contest implementation; this lesson uses Edmonds–Karp (BFS augmenting paths) so the invariant is visible.
function maxFlow(cap, s, t) {
const n = cap.length;
const res = cap.map((row) => row.slice());
function bfs() {
const par = Array(n).fill(-1);
par[s] = s;
const q = [s];
for (let qi = 0; qi < q.length; qi++) {
const u = q[qi];
for (let v = 0; v < n; v++) {
if (par[v] === -1 && res[u][v] > 0) {
par[v] = u;
q.push(v);
}
}
}
return par;
}
let flow = 0;
let par;
while ((par = bfs()) && par[t] !== -1) {
let add = Infinity;
for (let v = t; v !== s; v = par[v]) add = Math.min(add, res[par[v]][v]);
for (let v = t; v !== s; v = par[v]) {
res[par[v]][v] -= add;
res[v][par[v]] += add;
}
flow += add;
}
return flow;
}Checks 0/2