通常解决网络流问题的思路是将问题转化为流网络，并通过最大流、最小割或费用流等方法求解原问题与流网络之间的数量关系。
网络流算法与其他算法不同，需要熟记概念和定理，否则在解题过程中会遇到较大障碍。
1. 流网络
一个流网络记作\(G=(V,E)\)，其中\(V\)表示点集，\(E\)表示边集。对于所有\((u,v)\in E\)，都有一个容量记作\(c(u,v)\)。流网络还包括源点和汇点，通常记作\(s,t\)。
如图所示，这是一个流网络示例。
2. 可行流
对于每一个流网络，满足以下两个条件为可行流：
-
容量限制：记作：\(0\le f(u,v) \le c(u,v)\)，即流经每条边的流量不能超过其限制。
-
流量守恒：记作：\(\sum_{(v,x)\in E}f(v,x)=\sum_{(x,v)\in E}f(x,v)\)，即除了源点与汇点之外，流入点\(i\)的总流量等于流出点\(i\)的总流量。
可行流的流量\( |f| \)是指从源点流出的总流量，即：\( |f|=\sum_{(s,v)\in E}f(s,v)-\sum_{(v,s)\in E}f(v,s) \)。
3. 残留网络
一般来说，残留网络记作\(G_f=(V,E+!E)\)，其中\(V,E\)是源网络的边集和点集，\(!E\)表示\(E\)中的所有反向边。
定理
若\(f\)为原网络的可行流，\(f’\)为残留网络的可行流，则\(f+f’\)也是\(G\)的一个可行流且\( |f+f’|=|f|+|f’| \)。
证明：定义\(f_{n}=f+f’\)，则\(f_n(u,v)=f(u,v)+f'(u,v)\)（注意这里只考虑正向边）。为了证明也是一个可行流，无非从两方面：容量限制和流量守恒。
4. 增广路径
在残留网络中，沿着容量大于\(0\)的边如果能够走到终点，这条路径称为增广路径。（注意：增广路径只是一条路径，而非一个网络）
5. 割
5.1 定义
将点集\(V\)分成不重叠的\(S\)和\(T\)，使得源点在\(S\)，汇点在\(T\)。
5.2 割的容量
\(c(S,T)=\sum_{u\in S}\sum_{v\in T} c(u,v)\)
最小割：最小的割的容量
5.3 割的流量
\(f(S,T)=\sum_{u\in S}\sum_{v\in T} f(u,v)-\sum_{v\in S}\sum_{u\in T} f(u,v)\)
性质1：\(\forall [S,T], f(S,T)\le c(S,T)\)
证明：由于\(f(u,v)\)是大于等于0的，所以\(f(S,T)\le \sum_{u\in S}\sum_{v\in T} f(u,v)\)，又因为有容量，所以一定\(\le \sum_{u\in S}\sum_{v\in T} c(u,v)\)，故\(\forall [S,T], f(S,T)\le c(S,T)\)
性质2：\(\forall [S,T], f(S,T)= |f|\)
证明2：
\(f(X,Y)=\sum_{u\in X}\sum_{v\in Y} f(u,v)-\sum_{v\in X}\sum_{u\in Y} f(u,v)\)
则：\(f(X,Y)=-f(Y,X)\)，\(f(X,X)=0\)，\(f(Z,X\cup Y)=f(Z,X)+f(Z,Y), X\cap Y= \varnothing\)
那么有：
那么\( |f|=f(S,T)\le c(S,T)\)
即，\( |f|\le c(S,T)\)；故，最大流\(\le\)最小割
7. 最大流最小割定理
（1）可行流\(f\)是最大流
（2）\(G_f\)中不存在增广路
（3）\( |f|=c(S,T)\)
在三个条件中，仅需知道\(1\)个，就能够推出另外\(2\)个，证明略。
