Introduction to Network Flow

A flow network models a divisible resource moving through directed connections with limited capacities. A road network may carry traffic, a pipe network water, or an assignment network one unit per worker. A source s supplies the resource and a sink t receives it. Maximum flow asks for the largest possible net delivery, not the shortest route. The key modeling skill is separating capacity (what could travel) from flow (what currently travels). This first program checks a proposed flow and finds a residual augmenting path; later lessons repeatedly use such paths to optimize it.

Prerequisites: Graph fundamentals; Breadth-first search. Difficulty: Advanced. Review: Graph fundamentals, Breadth-first search.

Build the idea

1. 1. State the feasibility rules

   For each input edge e, require 0 ≤ f[e] ≤ capacity[e]. At every vertex other than s and t, incoming flow must equal outgoing flow. The flow value is outgoing minus incoming at s, equal to incoming minus outgoing at t. Counting only edges leaving s is wrong when input contains incoming edges to s. The program stores balance[v] = incoming − outgoing and checks these equalities before doing any residual search.

2. 2. Draw what remains possible

   For an edge u→v with capacity 3 carrying 2 units, the residual graph has a forward possibility u→v of 1 and a reverse possibility v→u of 2. The reverse arc means cancel two units of the earlier decision; it is not a new physical pipe. Keep residual arcs per original edge: a genuine input edge v→u is separate from this cancellation arc. Zero-capacity residual arcs cannot be traversed.

3. 3. Follow a small network

   Use the sample flow: 1→2 carries 2, 1→3 carries 1, 2→3 carries 0, 2→4 carries 2, and 3→4 carries 1. Vertex 2 receives and sends 2; vertex 3 receives and sends 1. Value is 3. In the residual graph, 1→3→4 has residual capacities 1 and 2, so one more unit can travel along it. BFS records parents and reconstructs that path.

   Original edge	Capacity	Flow	Forward residual	Reverse residual
   1→2	3	2	1	2
   1→3	2	1	1	1
   2→3	1	0	1	0
   2→4	2	2	0	2
   3→4	3	1	2	1

4. 4. Understand maximum flow and minimum cut

   A cut partitions vertices into S containing s and T containing t. Its capacity sums ORIGINAL capacities from S to T, excluding reverse-direction originals. Every feasible flow is at most that capacity: conservation cancels internal flow when summed over S. If no residual s→t path remains, vertices reachable from s define a cut whose outgoing originals are saturated and incoming originals carry zero flow. The current value equals this cut capacity, proving optimality. Lesson 5 constructs this certificate explicitly.

5. 5. Read the checker

   The input supplies capacities and proposed flows. Any violated capacity or conservation constraint prints INVALID; otherwise the program prints VALID and the net value. It builds positive residual arcs, searches from s, and prints an augmenting path if one exists. Finding a path proves the proposal is not maximum. Finding none certifies maximum only because feasibility was already checked; a residual search cannot repair an invalid flow.

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

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
using ll=long long;
int main(){
    int n,m,s,t;
    if(!(cin>>n>>m>>s>>t)){
        return 0;
    }
    vector<vector<int>>residual(n+1);
    vector<ll>balance(n+1,0);
    bool valid=true;
    for(int i=0;i<m;++i){
        int u,v;
        ll c,f;
        cin>>u>>v>>c>>f;
        if(c<0||f<0||f>c){
            valid=false;
        }
        balance[u]-=f;
        balance[v]+=f;
        if(f<c){
            residual[u].push_back(v);
        }
        if(f>0){
            residual[v].push_back(u); // Allows cancellation.
        }
    }
    for(int v=1;v<=n;++v){
        if(v!=s&&v!=t&&balance[v]!=0){
            valid=false;
        }
    }
    ll value=-balance[s];
    if(value<0||balance[t]!=value){
        valid=false;
    }
    if(!valid){
        cout<<"INVALID\n";
        return 0;
    }
    cout<<"VALID "<<value<<'\n';
    vector<int>parent(n+1,-1);
    queue<int>q;
    parent[s]=s;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int u:residual[v]){
            if(parent[u]==-1){
                parent[u]=v;
                q.push(u);
            }
        }
    }
    if(parent[t]==-1){
        cout<<"MAXIMUM\n";
        return 0;
    }
    vector<int>path;
    for(int v=t;v!=s;v=parent[v]){
        path.push_back(v);
    }
    path.push_back(s);
    reverse(path.begin(),path.end());
    cout<<"AUGMENTING PATH\n";
    for(int i=0;i<(int)path.size();++i){
        cout<<path[i]<<(i+1==(int)path.size()?'\n':' ');
    }
}

Complexity analysis

O(V+E) time: read each edge once, check every vertex, and scan each positive residual arc once in BFS. O(V+E) memory stores balances, parents, queue and at most two residual arcs per original edge. This program validates one flow; it does not compute a maximum by repeated augmentation.

Example input and output

Read n m s t, then m lines u v capacity proposedFlow. n≥2, valid labels, s≠t; absolute capacity/flow totals fit long long. Print INVALID or VALID value, then MAXIMUM or AUGMENTING PATH and its vertex sequence.

Input

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

Output

VALID 3
AUGMENTING PATH
1 3 4

The proposal delivers three units. Vertex 3 can accept one additional unit from 1 and send it to 4; the bottleneck is residual capacity 1 on 1→3.

Practical applications

Use network flow when local capacity constraints and conservation describe the whole problem: transportation, scheduling, disjoint paths and bipartite assignment. For one cheapest route, use shortest paths instead. For costs attached to transported units, study minimum-cost flow. Node capacities can be modeled by splitting a vertex into an in-vertex and out-vertex joined by a capacity edge.

Check your understanding

Why does a residual reverse edge have capacity equal to the current forward flow?

Put it into practice

Change the checker to print the residual-reachable set when a proposed feasible flow is maximum.