首先是一些关于网络流的术语：
源点：即图的起点。
汇点：即图的终点。
容量：有向边(u,v)允许通过的最大流量。
增广路：一条合法的从源点流向汇点的路径。
网络流问题是在图上进行解决的，我们通常可以将问题转化为：
给定一个有向图,每条边有一个容量，有两个点被标记做了源点与汇点，你要确定尽量多的从源点到汇点的路径，每条边被经过的次数不得超过它的容量。我们将一个合法解称作一个流,一条边被经过的次数称作其流量，最终流的总和称作整个流的流量。
我们的限制转化为:
每条边被经过的次数不得超过它的容量->每条边的流量不超过其流量，流由若干从源点到汇点的路径组成->除源点和汇点外,对于每个点,流入它的流量和等于从它流出的流量和。最大化整个流的流量->最大化从源点流出的流量。
前两个条件分别被称为容量限制和流量平衡。
可以显然地想到一个(不正确的)解法,即不停地找一条任意的路径并流过去。
如何做到"可以反悔"呢？
减少一条边上k的流量，相当于反向流过来k的流量。这个还是比较显然的。假设你把一些货物从a地运到b地,后来你发现运错了,那就再运回来就行了。定义一条边的残量,是指它还能流多少流量(即容量减去当前流量)。
刚刚的反思告诉我们:
在一条边流过去之后，我们需要反过来建一条边。如果边u流过去了一些流量，那么我们需要建一条反过来的边，比如叫做v。v的残量即为u当前的流量。沿着v流一些流量，对应到原问题中相当于在u这条边上少流了一些流量。这就是网络流最大流的核心思想。
FF方法
(1)在残量网络上找到一条从源点到汇点的道路(称为"增广路")
(2)取增广路上残量最小值v
(3)将答案加上v
(4)将增广路上所有边的残量减去v，而它们的反向边的残量加上v。
重复这个过程直到找不到增广路，就可以求出最大流。
步骤4中,一条边的反向边的反向边即为这条边本身(即它们两个互为反向边)。
首先这个算法是不会死循环的,因为每次增广都导致流量增加(并且增加的是整数),而流量有一个客观存在的最大值,所以它必定结束。
由于他没有指定存在多条增广路的时候选哪一条,所以我们先考虑最简单的情况:随便找一条。
经过实践,我们可以想到只增广最短路径。
然后讲一下EK算法：
EK算法
是FF的一种实现:每次寻找增广路增广。可以证明其复杂度是O((m^2)*n)的。
首先我们考虑该如何建反向边：
我们选择用邻接表存边（邻接矩阵受数据范围限制，一般无法开心的使用），那么反向边的编号该如何处理，才能使这两条边相互关联起来？
答案之一就是异或（不会请自行百科）:
0^1 = 1, 1^1 = 0;
2^1 = 3, 3^1 = 2;
4^1 = 5, 5^1 = 4;
于是我们发现，异或1这一操作，可以将相邻的两个整数关联起来（偶数在前，奇数在后），然后我们可以选择从零开始存在，完美解决存边问题。
至于算法的核心思想，其实就是FF方法，只是进行了具体实现。
来一波核心代码：
int EK(int s, int t) //s为源点，为汇点 { int DIS = 0; //DIS用来记每次BFS找到的增广路的最大流量 int ans = 0; //ans用来记最终答案 while ((DIS = BFS(s, t)) != -1) { int cur = t; while (cur != s)//根据BFS得出的前驱（pre）数组遍历路径，更改容量 { e[pre[cur]].w -= DIS; e[pre[cur] ^ 1].w += DIS; cur = e[pre[cur]].from; } ans += DIS; } return ans; //返回答案 }
BFS的任务是得出的前驱（pre）数组（就是一条增广路），并记录到每个点为止的最大流量（flow）数组。
BFS找到一条增广路就应该返回。且不走重点（否则复杂度将无法承受）。
完整代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <queue> #include <cctype> using namespace std; const int MAXN = 10010; const int INF = 99999999; struct Edge { int from; int to; int w; int next; }e[MAXN << 5]; int n, m, s, t, x, y, z; int cnt = -1; int f[MAXN]; int pre[MAXN]; int flow[MAXN]; queue <int> q; int min(int a, int b) { if (a <= b) return a; else return b; } int read() { int x = 0; int k = 1; char c = getchar(); while (!isdigit(c)) if (c == '-') k = -1, c = getchar(); else c = getchar(); while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); return k * x; } int BFS(int s, int t) { while (!q.empty()) q.pop(); memset(pre, -1, sizeof(pre)); memset(flow, 0x7f, sizeof(flow)); pre[s] = 0; q.push(s); flow[s] = INF; while (!q.empty()) { int cur = q.front(); q.pop(); if (cur == t) break; for (int i = f[cur]; i != -1; i = e[i].next) { if (pre[e[i].to] == -1 && e[i].w > 0) { pre[e[i].to] = i; flow[e[i].to] = min(flow[cur], e[i].w); q.push(e[i].to); } } } if (pre[t] == -1) return -1; return flow[t]; } void Add_edge(int from, int to, int w) { ++cnt; e[cnt].from = from; e[cnt].to = to; e[cnt].w = w; e[cnt].next = f[from]; f[from] = cnt; } int EK(int s, int t) { int DIS = 0; int ans = 0; while ((DIS = BFS(s, t)) != -1) { int cur = t; while (cur != s) { e[pre[cur]].w -= DIS; e[pre[cur] ^ 1].w += DIS; cur = e[pre[cur]].from; } ans += DIS; } return ans; } int main() { n = read(); m = read(); s = read(); t = read(); memset(f, -1, sizeof(f)); for (int i = 1; i <= m; ++i) { x = read(); y = read(); z = read(); Add_edge(x, y, z); Add_edge(y, x, 0); } cout << EK(s, t); char c = getchar(); return 0; }