Maximum Flow–Minimum Cut Theorem

The maximum flow–minimum cut theorem connects routing and separation: the largest deliverable flow equals the cheapest capacity of edges separating source from sink. It gives an optimality certificate rather than only a numeric answer. A maximum-flow solution is a lower bound on what can be delivered; a cut is an upper bound. When they coincide, both are optimal. This lesson recovers an actual minimum cut from a completed residual network.

Prerequisites: Dinic's Algorithm; Introduction to Network Flow. Difficulty: Advanced. Review: Dinic's Algorithm.

Build the idea

1. 1. Define a directed cut precisely

   Choose a set S containing s but not t. T is every other vertex. Cut capacity is the sum of original capacities on edges from S to T, counting parallel edges separately. Edges from T to S are not added. A directed flow crossing the boundary in the reverse direction decreases net delivery, which is why counting all incident edges gives the wrong bound.

2. 2. Derive the upper bound

   Sum conservation over vertices in S except the source. Internal contributions cancel in pairs. Flow value equals total flow from S to T minus total flow from T to S. Outgoing flow is at most outgoing capacity and incoming flow is nonnegative. Therefore value ≤ capacity(S,T) for every feasible flow and every cut. This argument needs neither integrality nor a particular augmenting-path policy.

3. 3. Use the final residual search

   Run Dinic to completion, then BFS from s through strictly positive RESIDUAL arcs. Mark the reachable set as S. Because no augmenting path exists, t is in T. An original S→T edge must have zero forward residual capacity, hence be saturated. An original T→S edge must carry zero flow: otherwise its reverse residual arc would lead from S into T. Substitute these facts into the boundary-flow equation to obtain equality.

4. 4. Recover original edges, not residual partners

   Store the input edges with their original capacity and endpoints before changing the residual graph. Scan them after reachability; report precisely those whose tail is in S and head outside S. The program prints maximum flow, recovered cut capacity, then the count and 1-based input IDs of crossing edges. Zero-capacity crossing edges may be reported; they do not change the sum. Cut edges need not form a path or touch the source.

5. 5. Inspect the example and nonuniqueness

   In the sample all edges leaving 1 are saturated, so only vertex 1 remains reachable. S={1}, T={2,3,4}, and crossing input edges are 1 and 2 with capacities 3 and 2. Their sum 5 equals the computed flow. Different networks may have several minimum cuts; residual reachability returns one valid cut, not every possible one. If no initial route exists, flow and minimum-cut capacity are both zero.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<limits>
using namespace std;
using ll=long long;
struct Edge{
    int to;
    ll cap;
};
vector<Edge>edges;
vector<vector<int>>graph;
void addEdge(int u,int v,ll cap){
    int id=(int)edges.size();
    edges.push_back({v,cap});
    edges.push_back({u,0}); // Reverse residual edge starts empty.
    graph[u].push_back(id);
    graph[v].push_back(id^1); // Works even for self-loops and parallel edges.
}
vector<int>level,nextEdge;
bool buildLevels(int n,int s,int t){
    level.assign(n+1,-1);
    queue<int>q;
    level[s]=0;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int id:graph[v]){
            int u=edges[id].to;
            if(edges[id].cap>0&&level[u]==-1){
                level[u]=level[v]+1;
                q.push(u);
            }
        }
    }
    return level[t]!=-1;
}
ll send(int v,int t,ll limit){
    if(v==t){
        return limit;
    }
    for(int&i=nextEdge[v];i<(int)graph[v].size();++i){
        int id=graph[v][i],u=edges[id].to;
        if(edges[id].cap==0||level[u]!=level[v]+1){
            continue;
        }
        ll pushed=send(u,t,min(limit,edges[id].cap));
        if(!pushed){
            continue;
        }
        edges[id].cap-=pushed;
        edges[id^1].cap+=pushed;
        return pushed;
    }
    return 0;
}
ll maxFlow(int n,int s,int t){
    ll answer=0;
    while(buildLevels(n,s,t)){
        nextEdge.assign(n+1,0);
        // Reuse this level graph until every s-t path in it is blocked.
        while(ll pushed=send(s,t,numeric_limits<ll>::max())){
            answer+=pushed;
        }
    }
    return answer;
}
int main(){
    int n,m,s,t;
    if(!(cin>>n>>m>>s>>t)){
        return 0;
    }
    graph.resize(n+1);
    struct Original{
        int u,v,id;
        ll cap;
    };
    vector<Original>original;
    for(int i=0;i<m;++i){
        int u,v;
        ll c;
        cin>>u>>v>>c;
        original.push_back({u,v,(int)edges.size(),c});
        addEdge(u,v,c);
    }
    ll value=maxFlow(n,s,t);
    vector<char>reachable(n+1,false);
    queue<int>q;
    q.push(s);
    reachable[s]=true;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int id:graph[v]){
            if(edges[id].cap>0&&!reachable[edges[id].to]){
                reachable[edges[id].to]=true;
                q.push(edges[id].to);
            }
        }
    }
    ll capacity=0;
    vector<int>cut;
    for(int i=0;i<m;++i){
        if(reachable[original[i].u]&&!reachable[original[i].v]){
            capacity+=original[i].cap;
            cut.push_back(i+1);
        }
    }
    cout<<value<<'\n'<<capacity<<'\n';
    cout<<cut.size();
    for(int id:cut){
        cout<<' '<<id;
    }
    cout<<'\n';
}

Complexity analysis

Dinic costs O(V²E) in general. Once flow is maximum, residual reachability and scanning original edges add O(V+E) time and O(V+E) memory including the original edge list. Extracting a cut itself does not require another flow run. The theorem applies beyond integer capacities, but this program uses exact integer residual updates.

Example input and output

Read n m s t, then m directed edges u v capacity. Vertices are 1..n, n≥2, s≠t. Parallel and opposite-direction edges are allowed. Capacities are nonnegative integers; total capacity leaving s fits long long (at most 10^15 here). Output the maximum flow value. Instead of only one value, output the flow, cut capacity, and a line containing k followed by the k crossing input-edge IDs.

Input

4 5 1 4
1 2 3
1 3 2
2 3 1
2 4 2
3 4 3

Output

5
5
2 1 2

Only source 1 is residual-reachable. Original edges 1→2 and 1→3 form a cut of capacity 3+2=5, matching the flow.

Practical applications

Use the theorem for minimum-cost edge removal, bottleneck explanations, disjoint path proofs and weighted separation reductions. Vertex-removal costs require vertex splitting. For undirected cuts, model each undirected edge with both directed capacities and interpret the final boundary carefully. Global minimum cut without a specified s,t is a different problem.

Check your understanding

Which graph determines the recovered source-side set?

Put it into practice

Extend the output to list all vertices of the source-side partition.