How to Implement Max Flow and Min Cut Algorithms in Competitive Programming

To solve max flow and min cut problems in competitive programming, construct a residual graph with forward and backward edges, execute Dinic's algorithm for O(E√V) practical complexity, and derive the minimum cut by performing a BFS from the source on the final residual network.

Network flow algorithms form the backbone of advanced competitive programming graph theory, providing solutions to bipartite matching, path cover, and resource allocation problems. By the max-flow min-cut theorem, computing the maximum flow from a source s to a sink t simultaneously yields the capacity of the minimum s-t cut, making these algorithms doubly useful for contest problems. The hzwer/shareoi repository offers authoritative lecture notes and reference implementations that demonstrate exactly how to code these structures in C++ under strict time and memory limits.

Understanding the Max-Flow Min-Cut Theorem

The theoretical foundation states that in any flow network, the maximum amount of flow passing from source to sink equals the total weight of the minimum capacity cut separating the source from the sink. In implementation terms, this means once you compute the maxflow, you automatically possess the value of the mincut. The residual graph—storing remaining capacities on forward edges and flow values on reverse edges—serves as the central data structure enabling both calculations.

Algorithm Selection for Contest Performance

While several algorithms exist, competitive programming contexts demand specific trade-offs between implementation complexity and runtime guarantees.

Dinic's Algorithm (Preferred for General Contests)

Dinic's algorithm achieves O(E√V) on unit-capacity graphs and O(EV²) in the worst case, though it typically runs much faster on contest data. It constructs a level graph via BFS, then finds blocking flows using DFS with current-edge optimization. According to the hzwer/shareoi materials, this balance of simplicity and speed makes it the default choice for most regional and international olympiad problems.

Push-Relabel and ISAP for Dense Graphs

For scenarios involving dense graphs or very large capacities, the push-relabel method with gap heuristic or ISAP (Improved Shortest Augmenting Path) can outperform Dinic's by reducing the overhead of level graph reconstruction. However, these require more complex pointer maintenance and are typically only necessary for specialized problem constraints.

C++ Implementation Pattern

The repository emphasizes a specific structural pattern for flow implementations that fits within typical 1 KB source limits while maintaining clarity.

The Edge and Graph Structure

Store edges using a struct that maintains both forward and reverse pointers, enabling O(1) residual capacity updates during augmentation.

struct Dinic {
    struct Edge {
        int to, rev;
        long long cap;
    };
    int n, s, t;
    vector<vector<Edge>> g;
    vector<int> level, it;
    
    Dinic(int n) : n(n), g(n), level(n), it(n) {}
    
    void addEdge(int u, int v, long long cap) {
        Edge a{v, (int)g[v].size(), cap};
        Edge b{u, (int)g[u].size(), 0};
        g[u].push_back(a);
        g[v].push_back(b);
    }
    // ... BFS, DFS, maxflow methods
};

Note the use of long long for capacities to prevent overflow on large constraint problems, and the rev index that points to the corresponding reverse edge for O(1) residual updates.

Complete Dinic Implementation

The following full implementation from the repository handles the standard workflow: level graph construction, blocking flow DFS, and flow accumulation.

struct Dinic {
    struct Edge {int to, rev; long long cap;};
    int n, s, t;
    vector<vector<Edge>> g;
    vector<int> level, it;
    Dinic(int n) : n(n), g(n), level(n), it(n) {}

    void addEdge(int u, int v, long long cap) {
        Edge a{v, (int)g[v].size(), cap};
        Edge b{u, (int)g[u].size(), 0};
        g[u].push_back(a);
        g[v].push_back(b);
    }

    bool bfs() {
        fill(level.begin(), level.end(), -1);
        queue<int> q; q.push(s); level[s]=0;
        while(!q.empty()){
            int v=q.front(); q.pop();
            for(const auto& e:g[v])
                if(e.cap>0 && level[e.to]==-1){
                    level[e.to]=level[v]+1;
                    q.push(e.to);
                }
        }
        return level[t]!=-1;
    }

    long long dfs(int v, long long f){
        if(v==t) return f;
        for(int &i=it[v]; i<(int)g[v].size(); ++i){
            Edge &e=g[v][i];
            if(e.cap>0 && level[e.to]==level[v]+1){
                long long ret=dfs(e.to, min(f, e.cap));
                if(ret){
                    e.cap-=ret;
                    g[e.to][e.rev].cap+=ret;
                    return ret;
                }
            }
        }
        return 0;
    }

    long long maxflow(int S, int T){
        s=S; t=T;
        long long flow=0, aug;
        while(bfs()){
            fill(it.begin(), it.end(), 0);
            while((aug=dfs(s, LLONG_MAX))) flow+=aug;
        }
        return flow;
    }

    vector<int> minCutSide(){
        vector<int> vis(n,0); queue<int> q; q.push(s); vis[s]=1;
        while(!q.empty()){
            int v=q.front(); q.pop();
            for(const auto& e:g[v])
                if(e.cap>0 && !vis[e.to]){
                    vis[e.to]=1; q.push(e.to);
                }
        }
        return vis;
    }
};

Extracting the Minimum Cut

After computing maxflow, the residual graph contains saturated edges that form the cut boundary. To identify which vertices belong to the source side of the minimum cut, perform a BFS or DFS from the source traversing only edges with positive residual capacity. The minCutSide() method above returns a boolean vector where true indicates membership in the source partition. Edges from a true vertex to a false vertex constitute the min-cut set.

Modeling Techniques from the Repository

The hzwer/shareoi repository contains specific lecture files that teach how to translate abstract problems into flow networks.

• 网络流_周聿浩 & 黄哲威.pdf: Covers fundamental flow network formulation, residual graph mechanics, and the theory of augmenting paths.

• 网络流建模_周尚彦.pdf: Demonstrates practical reductions including bipartite matching, path cover in DAGs, project selection with profits, and circulation problems with lower bounds.

• 线性规划与网络流_曹钦翔.pptx: Explores the relationship between linear programming and flow, essential for advanced constraints like multiple sources or cost-based optimizations.

• 图论基础与网络流习题集锦_朱睿.pptx: Provides a curated collection of practice problems requiring max-flow and min-cut solutions, suitable for testing implementations.

• 网络流_未知作者.ppt: Offers additional visualizations and algorithmic examples for complex flow scenarios.

Summary

• Max-flow equals min-cut by the max-flow min-cut theorem; computing one yields the value of the other.
• Dinic's algorithm provides the best balance of implementation speed and theoretical bounds for competitive programming, typically running in O(E√V) on contest data.
• Residual graph representation requires storing reverse edge indices to enable O(1) flow updates during augmentation.
• Min-cut extraction involves traversing the residual graph from the source after max-flow completion to identify the source-side vertex partition.
• Modeling resources in hzwer/shareoi provide specific patterns for bipartite matching, project selection, and constrained circulation problems.

Frequently Asked Questions

What is the difference between max flow and min cut?

The max flow is the greatest amount of flow that can be sent from source to sink without exceeding edge capacities. The min cut is the partition of vertices into two sets separating source from sink with the minimum total capacity of edges crossing between sets. By the max-flow min-cut theorem, these values are always equal, though the flow assignment and the cut edges are different structural outputs.

Why does Dinic's algorithm outperform Edmonds-Karp in contests?

Dinic's algorithm constructs level graphs and finds blocking flows in phases, achieving O(E√V) on unit networks and O(EV²) worst-case, whereas Edmonds-Karp runs in O(VE²) and may recompute shortest paths unnecessarily. The current-edge optimization in Dinic's DFS further reduces constant factors, making it significantly faster on the large input sizes typical of programming competitions.

How do I handle multiple sources or sinks in a flow problem?

Create a super source connected to all original sources with infinite capacity edges, and a super sink connected from all original sinks with infinite capacity edges. Run the max-flow algorithm from the super source to the super sink; the result equals the sum of flows from all original sources to sinks. As noted in 线性规划与网络流_曹钦翔.pptx, this reduction maintains correctness while using standard single-source single-sink code.

What data type should I use for flow capacities?

Always use long long (64-bit integers) for capacities and flow values. Competitive programming problems frequently specify constraints where total flow exceeds 2³¹−1, causing 32-bit int overflow. The Dinic struct above explicitly declares long long cap and long long return types for maxflow to prevent runtime errors on large networks.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}