最大流目前了解两种算法，一个是ek(n * m2)，一个是dinic(n2 * m)。dinic算得上是ek的升级版。
对于最大流算法，网上有很多优秀的解释，这里就说自己做题的过程中遇到的一些问题。
在实际运用中，dinic有很多小优化。有一个优化只是一条语句，但对时间影响巨大。下面给出ac代码。
（我的代码用了vector[]存图，实际上有用三个int[]存图的做法）
#pragma warning(disable:4996)
#pragma warning(disable:6031)
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
constexpr int MAXN = 200;
constexpr int MAXF = 2147483647;
typedef struct _EDGE {
int v;
int r; // r = f - c
int i_redge;
}EDGE;
int N, M, S, T;
vector<EDGE> edges[MAXN];
unsigned char vis[MAXN];
unsigned int layer[MAXN];
void bfs();
long long dfs(int s, int t, int now);
long long dinic();
int main()
{
freopen("lg9.txt", "r", stdin);
// tmep
int i;
int u, v, f, iu, iv;
EDGE e = { 0, 0, 0 };
// v
long long ans;
// input
scanf("%d %d %d %d", &N, &M, &S, &T);
S--; T--;
for (i = 0; i < M; i++) {
scanf("%d %d %d", &u, &v, &f);
u--; v--;
iu = edges[u].size(); iv = edges[v].size();
e.v = v; e.r = f; e.i_redge = iv;
edges[u].push_back(e);
e.v = u; e.r = 0; e.i_redge = iu;
edges[v].push_back(e);
}
// count
ans = dinic();
printf("%lld\n", ans);
return 0;
}
void bfs()
{
queue<int> que;
int i, l, n, u, v;
EDGE e;
memset(vis, 0, N);
memset(layer, 0, N);
vis[S] = 1;
layer[S] = 1;
que.push(S);
while (!que.empty()) {
u = que.front();
que.pop();
n = edges[u].size();
l = layer[u] + 1;
for (i = 0; i < n; i++) {
if (edges[u][i].r == 0)
continue;
v = edges[u][i].v;
if (vis[v])
continue;
vis[v] = 1;
layer[v] = l;
que.push(v);
}
}
}
long long dfs(int s, int t, int now)
{
int i, l1, n, v;
int sub_flow;
long long flow = 0;
// end
if (s == t)
return now;
n = edges[s].size();
l1 = layer[s] + 1;
for (i = 0; i < n && now; i++) { // && now 优化1
v = edges[s][i].v;
if (layer[v] == l1 && edges[s][i].r) { // edges[s][i].r 优化2
sub_flow = dfs(v, t, min(now, edges[s][i].r));
if (sub_flow) {
edges[s][i].r -= sub_flow;
edges[v][edges[s][i].i_redge].r += sub_flow;
now -= sub_flow;
flow += sub_flow;
}
else {
layer[v] = 0; // = 0 优化3
}
}
}
return flow;
}
long long dinic()
{
long long ans = 0;
while (true) {
bfs();
if (!vis[T])
break;
ans += dfs(S, T, MAXF);
}
return ans;
}
首先最重要的优化肯定就是当前弧，一般来说实现方式是用变量记录当前遍历到那个边，我没试过这种方法，这里参考了下面列出的一篇文章，直接去掉dfs的提前返回来达到同样目的。
然后接下来有三个优化，实际上都算是dfs剪枝。
第二个优化在边比较少的图中有时可以起到时间减半的效果，其目的是当下一条弧已经没有剩余流量时，就不向这条弧dfs下去了。
第一个优化在边多的图中我测试出有一定效果，是洛谷讨论区的dalao分享的一个点。其目的来到当前点的那条弧已经没有流量时，当前点就没必要继续dfs下去了。
第三个优化在边多的图中很有效果，如果不加的话，在后面的轮次中，许多弧已经没有流量，变成了稀疏图，bfs出来的层次也非常深，此时时间会飞速上升。剪枝的原因是sub_flow代表从下一条弧出发到终点的所有可能路径的最大流之和，如果为0就代表走点v这条弧以后最大流为0，也就是说，v到终点实际上已经走不通了。所以接下来同级的遍历也不需要经过v了，根据初始条件，所有点layer>=1，==1是起点，只有>=2的点有机会被遍历，设置为0就可以达到不让任何点走进点v的目的。
参考
求解最大流的四种算法介绍、利用最大流模型解题入门syddf-CSDN博客最大流算法
(参考文章遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。)
