Network Flow Concepts — Max Flow and Min Cut Overview

from collections import deque, defaultdict

def max_flow(n, cap, s, t):
    def bfs(parent):
        visited = set([s])
        q = deque([s])
        while q:
            u = q.popleft()
            if u == t: return True
            for v in range(n):
                if v not in visited and cap[u][v] > 0:
                    visited.add(v)
                    parent[v] = u
                    q.append(v)
        return False

    flow = 0
    while True:
        parent = [-1]*n
        if not bfs(parent): break
        path_flow = float('inf')
        v = t
        while v != s:
            u = parent[v]
            path_flow = min(path_flow, cap[u][v])
            v = u
        v = t
        while v != s:
            u = parent[v]
            cap[u][v] -= path_flow
            cap[v][u] += path_flow
            v = u
        flow += path_flow
    return flow

function maxFlow(n, cap, s, t) {
    const bfs=(par)=>{
        const vis=new Set([s]),q=[s];
        while(q.length){const u=q.shift();if(u===t)return true;for(let v=0;v<n;v++)if(!vis.has(v)&&cap[u][v]>0){vis.add(v);par[v]=u;q.push(v);}}
        return false;
    };
    let flow=0;
    while(true){
        const par=new Array(n).fill(-1); if(!bfs(par))break;
        let pf=Infinity,v=t;
        while(v!==s){const u=par[v];pf=Math.min(pf,cap[u][v]);v=u;}
        v=t; while(v!==s){const u=par[v];cap[u][v]-=pf;cap[v][u]+=pf;v=u;}
        flow+=pf;
    }
    return flow;
}

import java.util.*;
public int maxFlow(int n, int[][] cap, int s, int t) {
    int flow=0;
    while(true){
        int[] par=new int[n]; Arrays.fill(par,-1); par[s]=s;
        Queue<Integer>q=new LinkedList<>(); q.offer(s);
        while(!q.isEmpty()&&par[t]==-1){int u=q.poll();for(int v=0;v<n;v++)if(par[v]==-1&&cap[u][v]>0){par[v]=u;q.offer(v);}}
        if(par[t]==-1)break;
        int pf=Integer.MAX_VALUE; for(int v=t;v!=s;v=par[v])pf=Math.min(pf,cap[par[v]][v]);
        for(int v=t;v!=s;v=par[v]){cap[par[v]][v]-=pf;cap[v][par[v]]+=pf;}
        flow+=pf;
    }
    return flow;
}

#include <queue>
#include <vector>
#include <climits>
using namespace std;
int maxFlow(int n, vector<vector<int>>& cap, int s, int t) {
    int flow=0;
    while(true){
        vector<int>par(n,-1); par[s]=s; queue<int>q; q.push(s);
        while(!q.empty()&&par[t]==-1){int u=q.front();q.pop();for(int v=0;v<n;v++)if(par[v]==-1&&cap[u][v]>0){par[v]=u;q.push(v);}}
        if(par[t]==-1)break;
        int pf=INT_MAX; for(int v=t;v!=s;v=par[v])pf=min(pf,cap[par[v]][v]);
        for(int v=t;v!=s;v=par[v]){cap[par[v]][v]-=pf;cap[v][par[v]]+=pf;}
        flow+=pf;
    }
    return flow;
}

/* C: 2D capacity matrix + BFS augmenting path */