概述

我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。
最大流算法有很多种，基本上分为两类：
1.“增广路”算法。例如 Edmonds-Karp 算法、Dinic 算法、ISAP 算法。
2.“预流推进”算法。例如

Ford-Fulkerson 增广路方法

残留网络：
迭代后残留容量所产生的图，每次新的迭代在上一次的残留网络上进行。

增广路：
在残留网络上找到一条从 s 到 t 的路径。

Ford-Fulkerson 方法的运行时间依赖于增广路径的搜索次数。虽然用 BFS 或者 DFS 都行，但是 DFS 这种深度搜索模式可能陷入长时间的迭代，但如果用 BFS，几次就够了。

EK 算法

时间复杂度 ，一般能处理 ~ 规模的网络
用 BFS 来计算增广路径，就是 Edmonds-Karp 算法。

// 模板题（https://www.luogu.com.cn/problem/P3376）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 201;

long long graph[maxn][maxn];  // 邻接矩阵存图
int n, m, s, t, pre[maxn];
long long flow[maxn];

int bfs() {
    memset(flow, 0, sizeof flow);
    queue<int> q; q.push(s);
    pre[s] = -1, flow[s] = LLONG_MAX;
    while(!q.empty()) {
        int tp = q.front(); q.pop();
        if (flow[t]) continue;
        for(int i = 1; i <= n; ++ i) {
            if (flow[i] || !graph[tp][i]) continue;
            flow[i] = min(flow[tp], graph[tp][i]);
            pre[i] = tp;
            q.push(i);
        }
    }
    return flow[t];
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(graph, 0, sizeof graph);
    for(int i = 1; i <= m; ++ i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        graph[u][v] += w;
    }
    long long maxflow = 0;
    while(bfs()) {    //  每次bfsd都能找到一条增广路
        long long used = flow[t];
        for(int i = t; ~pre[i]; i = pre[i]) {
            graph[ pre[i] ][i] -= used;
            graph[i][ pre[i] ] += used;
        }
        maxflow += used;
    }
    printf("%lld\n", maxflow);
    return 0;
}

Dinic 算法

时间复杂度 ，一般能够处理 ~ 规模的网络
Dinic 算法 的过程是这样的：每次增广前，我们先用 BFS 来将图分层。如果不存在到汇点的增广路（即汇点的层数不存在），我们即可停止增广，并且确保我们找到的增广路是最短的。
Dinic 算法有几个优化：

1. 多路增广 ：每次找到一条增广路的时候，如果残余流量没有用完怎么办呢？我们可以利用残余部分流量，再找出一条增广路。这样就可以在一次 DFS 中找出多条增广路，大大提高了算法的效率。
2. 当前弧优化 ：如果一条边已经被增广过，那么它就没有可能被增广第二次。那么，我们下一次进行增广的时候，就可以不必再走那些已经被增广过的边。
3. 剪枝优化，有效代替当前弧优化，当一个点的流量跑满时，可把 d[x] 标记为 0，dfs 不再遍历该点。
4. 路径优化，把从 s 向 t 分层，改为 从 t 向 s 分层，可以省去很多多余步骤。

相较于EK算法，显然Dinic算法的效率更优也更快：虽然在稀疏图中区别不明显，但在稠密图中Dinic的优势便凸显出来了（所以Dinic算法用的更多），此外，Dinic算法求解二分图最大匹配的时间复杂度为
​

// 模板题（https://www.luogu.com.cn/problem/P3376）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 201;
const int maxm = 5001;

struct edge{
    long long to, next, cap, flow;  // 容量 和 流量
}e[maxm << 1]; int head[maxn], tot;
int n, m, s, t, d[maxn], cur[maxn]; // d[]分层，cur[]弧优化

void addedge(int u, int v, int w) {
    e[++tot] = {v, head[u], w, 0}, head[u] = tot;
    e[++tot] = {u, head[v], 0, 0}, head[v] = tot;
}

bool bfs() { // 分层 t-s路径优化
    memset(d, 0x3f, sizeof d);
    queue<int> q; q.push(t);
    d[t] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (d[j] == d[0] && e[i^1].cap > e[i^1].flow) {
                d[j] = d[x] + 1;
                if (j == s) return true;
                q.push(j);
            }
        }
    }
    return false;
}

long long dfs(int x, long long flow, long long used = 0) {
    if (x == t) return flow;
//    for(int i = cur[x]; ~i && flow != used; i = e[ cur[x] = i ].next) {  // 当前弧优化
    for(int i = head[x]; ~i && flow != used; i = e[i].next) {
        long long j = e[i].to, f;
        if (d[x] - 1 == d[j] && e[i].cap > e[i].flow) {
            f = dfs(j, min(e[i].cap-e[i].flow, flow-used));
            if (f) e[i].flow += f, e[i^1].flow -= f, used += f;
        }
    }
    if (!used) d[x] = 0;   // 剪枝优化
    return used;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(head, -1, sizeof head); tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
    }
    long long maxflow = 0;
    while(bfs()) {   // 每次dfs分层都能找到多条增广路
//        memcpy(cur, head, sizeof head);
        maxflow += dfs(s, INT_MAX);
    }
    printf("%lld\n", maxflow);
    return 0;
}

ISAP 算法

时间复杂度
ISAP算法，就是在Dinic算法上，进行了进一步优化，大概也是常见的最快的增广路算法了。
ISAP算法在这几个方面进行了大优化:

1. 引进了gap数组，优化了断层，一定程度上减少了不必要的时间损失
2. 你只需要一次bfs即可

当我们从终点向起点跑完bfs之后，就再也不需要重跑了。当我们遍历完一个节点，居然还剩下了一些流，那么我们只有将它的高度提高，才有可能在下一次遍历中把流推向其他边。不过这个算法最大的遗憾还是这张图：

很显然，按照ISAP算法，S的高度会不断提高8次才能开始从1增广。如果数据再强力一些，就有可能卡掉。

// 模板题（https://www.luogu.com.cn/problem/P3376）
#include<bits/stdc++.h>

using namespace std;

const int maxn = 201;
const int maxm = 5001;

struct node {
    long long to, next, cap, flow;
}e[maxm << 1]; int head[maxn], tot;
int n, m, s, t, d[maxn], cur[maxn];
int gap[maxn];   //  GAP优化

int bfs() {
    memset(d, 0, sizeof d);
    memset(gap, 0, sizeof gap);
    queue<int> q; q.push(t);
    gap[ d[t] = 1 ] = 1;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = head[x]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (!d[j] && e[i^1].cap > e[i^1].flow) {
                gap[ d[j] = d[x] + 1 ] ++;
                q.push(j);
            }
        }
    }
    return 0;
}

long long dfs(int x, long long flow) {
    if(x == t) return flow;
    long long used = 0;
    for(int &i = cur[x]; ~i; i = e[i].next) { // 弧优化
        int j = e[i].to;
        if (d[x] - 1 == d[j] && e[i].cap > e[i].flow) {
            long long low = dfs(j, min(e[i].cap-e[i].flow, flow-used));
            if (low) e[i].flow += low, e[i^1].flow -= low, used += low;
        }
        if (used == flow) return used;
    }
    (--gap[ d[x] ]) ? (++gap[ ++d[x] ]) : (d[s] = n+1);  // gap优化
    return used;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(head, -1, sizeof head), tot = -1;
    for(int i = 1; i <= m; ++ i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        e[++tot] = {v, head[u], w, 0}, head[u] = tot;
        e[++tot] = {u, head[v], 0, 0}, head[v] = tot;
    }
    long long maxflow = bfs();  // 一次反向dfs分层
    while(d[s] <= n) { // dfs若出现断层则退出
        memcpy(cur, head, sizeof head);
        maxflow += dfs(s, LLONG_MAX);
    }
    printf("%lld\n", maxflow);
    return 0;
}

预流推进

// 板子题 （https://www.luogu.com.cn/problem/P4722）
#pragma GCC optimize(3, "Ofast", "inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : * S ++)
char BB[1 << 20], *S = BB, *T = BB;
inline long long read() {
    char ch = getchar(); long long f = 1, x = 0;
    for(; ch>'9'||ch<'0'; ch=getchar()) if(ch=='-')f=-1;
    for(;ch<='9'&&ch>='0';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x * f;
}

const int maxn = 1e5+1;
const int INF(INT_MAX);

struct edge {
    int to,flow,next;
    edge(int to,int flow,int next):to(to),flow(flow),next(next) {}
};
std::vector<edge>a[maxn];
std::vector<int>list[maxn],h,cnt,que,e;
typedef std::list<int> List;
std::vector<List::iterator>iter;
List dlist[maxn+100];
typedef std::vector<edge>::iterator Iterator;
int hst,nowh;
void init(int n) {
    hst=0, nowh=0;
    h.clear(), cnt.clear(), que.clear(), e.clear();
    for(int i=1; i<=n; i++) a[i].clear();
}

inline void addEdge(const int u,const int v,const int f) {
    a[u].push_back(edge(v,f,a[v].size()));
    a[v].push_back(edge(u,0,a[u].size()-1));
}
inline void relabel(int n,int t) {
    h.assign(n,n);
    h[t]=0;
    cnt.assign(n,0);
    que.clear();
    que.resize(n+1);
    int qh=0,qt=0;
    for(que[qt++]=t; qh<qt;) {
        int u=que[qh++],het=h[u]+1;
        for(Iterator p=a[u].begin(); p!=a[u].end(); ++p) {
            if(h[p->to]==n&&a[p->to][p->next].flow>0) {
                cnt[h[p->to]=het]++;
                que[qt++]=p->to;
            }
        }
    }
    for(register int i=0; i<=n; ++i) {
        list[i].clear();
        dlist[i].clear();
    }
    for(register int u=0; u<n; ++u) {
        if(h[u]<n) {
            iter[u]=dlist[h[u]].insert(dlist[h[u]].begin(),u);
            if(e[u]>0)
                list[h[u]].push_back(u);
        }
    }
    hst=(nowh=h[que[qt-1]]);
}
inline void push(int u,edge &ed) {
    int v=ed.to;
    int df=std::min(e[u],ed.flow);
    ed.flow-=df;
    a[v][ed.next].flow+=df;
    e[u]-=df;
    e[v]+=df;
    if(0<e[v]&&e[v]<=df)
        list[h[v]].push_back(v);
}
inline void push(int n,int u) {
    int nh=n;
    for(Iterator p=a[u].begin(); p!=a[u].end(); ++p) {
        if(p->flow>0) {
            if(h[u]==h[p->to]+1) {
                push(u,*p);
                if(e[u]==0)
                    return;
            } else
                nh=std::min(nh,h[p->to]+1);
        }
    }
    int het=h[u];
    if(cnt[het]==1) {
        for(register int i=het; i<=hst; ++i) {
            for(List::iterator it=dlist[i].begin(); it!=dlist[i].end(); ++it) {
                cnt[h[*it]]--;
                h[*it]=n;
            }
            dlist[i].clear();
        }
        hst=het-1;
    } else {
        cnt[het]--;
        iter[u]=dlist[het].erase(iter[u]);
        h[u]=nh;
        if(nh==n)
            return;
        cnt[nh]++;
        iter[u]=dlist[nh].insert(dlist[nh].begin(),u);
        hst=std::max(hst,nowh=nh);
        list[nh].push_back(u);
    }
}
inline int hlpp(int n,int s,int t) {

    if(s==t)
        return 0;
    nowh=0;
    hst=0;
    h.assign(n,0);
    h[s]=n;
    iter.resize(n);
    for(register int i=0; i<n; ++i)
        if(i!=s)
            iter[i]=dlist[h[i]].insert(dlist[h[i]].begin(),i);
    cnt.assign(n,0);
    cnt[0]=n-1;
    e.assign(n,0);
    e[s]=INF;
    e[t]=-INF;
    for(register int i=0; i<(int)a[s].size(); ++i)
        push(s,a[s][i]);
    relabel(n,t);
    for(int u; nowh>=0;) {
        if(list[nowh].empty()) {
            nowh--;
            continue;
        }
        u=list[nowh].back();
        list[nowh].pop_back();
        push(n,u);
    }
    return e[t]+INF;
}

int main() {
    int n = read(), m = read(), s = read(), t = read();
    init(n);
    for(int i = 1; i <= m; ++ i) {
        int u = read(), v = read(), w = read();
        addEdge(u, v, w);
    }
    printf("%d\n",hlpp(n+1,s,t));
    return 0;
}

/*
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

7 14 1 7
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7

10 16 1 2
1 3 2
1 4 2
5 2 2
6 2 2
3 5 1
3 6 1
4 5 1
4 6 1
1 7 2147483647
9 2 2147483647
7 8 2147483647
10 9 2147483647
8 5 2
8 6 2
3 10 2
4 10 2

答案：50 14 8
*/