1. 最大流等于最小割
2. 可行流 <= 最大流 = 最小割 <= 任意割
3. 每次找增广路 // 至于为什么不全部一次性找完 而是每次找一个呢 可以参考星空大佬的博客
4. 网络流的时间复杂度一般是不会到理论上限的 就算超时加上 多路增广优化 和 炸点优化即可

3问题的参考 orz

// Ford-Fulkerson (链式前向星)
void add(int a,int b,int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

int dfs(int x,int flow){
    if(x == t) return flow; // 走到汇点 返回本次增广流量
    vis[x] = 1;
    for(int i = h[x];~i;i = ne[i]){
        int j = e[i];
        if(w[i] && !vis[j]){
            int t = dfs(y, min(flow, w[i]));
            if(t > 0){
                w[i] -= t, w[i ^ 1] += t;
                return t;
            }
        }
    }
    return 0;
}

while(memset(vis, 0, sizeof vis) && (res = dfs(s, 2e9)) > 0) ans += res;

printf("%d\n", ans);
----------------
// Dinic 对 FF 分层图优化
int s, t, flow;

bool bfs(){
    memset(d, 0, sizeof d);
    while(q.size()) q.pop();

    d[s] = 1; q.push(s);
    while(q.size()){
        auto t = q.front(); q.pop();
        for(int i = h[t];~i;i = ne[i]){
            // 有残留网络 并且没有被遍历过
            if(w[i] && !d[e[i]]){
                d[e[i]] = d[t] + 1;
                q.push(e[i]);
                if(e[i] == t) return 1; // 能到终点
            }
        }
    }
    return 0; // 不连通 即st割为0
}

int dinic(int x,int flow){
    if(x == t) return flow;
    int sum = 0;
    for(int i = h[x];~i;i = ne[i]){
        int j = e[i];
        if(w[i] && d[j] == d[x] + 1){
            int k = dinic(j, min(flow, w[i]));
            w[i] -= k, w[i ^ 1] += k;
            flow -= k, sum += k;
        }
    }

    if(!sum) d[x] = 0;
    return sum;
}

while(bfs())
    while(flow = dfs(s, 2e6))
        ans += flow;
// Dinic 当前弧优化
// 当一个点被榨干的时候 就把它删掉
int s, t, flow;
int cur[N];

bool bfs(){
    memcpy(cur, h, sizeof h);
    memset(d, 0, sizeof d);
    while(q.size()) q.pop();

    d[s] = 1; q.push(s);
    while(q.size()){
        auto t = q.front(); q.pop();
        for(int i = h[t];~i;i = ne[i]){
            // 有残留网络 并且没有被遍历过
            if(w[i] && !d[e[i]]){
                d[e[i]] = d[t] + 1;
                q.push(e[i]);
                if(e[i] == t) return 1; // 能到终点
            }
        }
    }
    return 0; // 不连通 即st割为0
}

int dinic(int x,int flow){
    if(x == t) return flow;
    int sum = 0;
    for(int i = cur[x];~i;i = ne[i]){
        cur[x] = i; // 当前弧优化
        int j = e[i];
        if(w[i] && d[j] == d[x] + 1){
            int k = dinic(j, min(flow, w[i]));
            w[i] -= k, w[i ^ 1] += k;
            flow -= k, sum += k;
        }
    }

    if(!sum) d[x] = 0; // 炸点优化
    return sum;
}

while(bfs())
    while(flow = dfs(s, 2e6))
        ans += flow;

// 多路增广优化
int dinic(int x,int flow){
    int a;
    if(x == t) return flow;
    int cost = 0;
    for(int &i = h[x];~i;i = ne[i]){
        int v = e[i];
        int r = w[i];
        if(d[v] == d[x] + 1 && w && (a = dfs(v, min(flow - cost, r)))){
            w[i] -= a, w[i ^ 1] += a;
            cost += a; // 汇聚各个方向的流量
            if(flow == cost) // 当某几个方向的流量相加等于当前最大流量的时候就无法对别的路进行增广了
                break;
        }
    }
    return cost;//返回当前汇聚的流量
}

EK

#define INF 0x3f3f3f3f
const int N = 10010;

int g[N][N], flow[N], pre[N];
int n, m;
queue<int> q;

int bfs(int s,int t){
    while(q.size()) q.pop();
    memset(pre, -1, sizeof pre);
    pre[s] = 0, flow[s] = INF;
    q.push(s);
    while(q.size()){
        int p = q.front(); q.pop();
        if(p == t) break;
        for(int i = 1;i <= n;i ++ ){
            if(i != s && pre[i] != -1 && g[p][i] > 0){
                pre[i] = p;
                flow[i] = min(flow[p], g[p][u]);
                q.push(i);
            }
        }
    }

    if(pre[t] == -1) return -1;
    return flow[t];
}

int EK(int s,int t){
    int sum = 0, delta = 0;
    while(1){
        delta = bfs(s, t);
        if(delta == -1) break; // 无增广路
        int p = t;
        while(p != s){
            g[pre[p]][p] -= delta;
            g[p][pre[p]] += delta;
            p = pre[p];
        }
        sum += delta;
    }

    return sum;
}

int ans = EK(1, n);

最小费用流(其实就是换成spfa就行)