图论中网络的相关概念见上篇博客
算法基本思想：
从某个初始流开始，重复地增加流的值到不能再改进为止，则最后所得的流将是一个最大流。为此，不妨将每条边上的流量设置为0作为初始流量。为了增加给定流量的值，我们必须找出从发点到收点的一条路并沿这条路增加流量。
当前流为最大流的充要条件：网络中不存在增广路
最大流最小截定理：在任何网络中，最大流的流量等于最小截集的容量。
整数流定理：在任何网络中，如果网络所有的弧容量都是整数，则存在整数最大流。
明确一点：最大流是指网络中流的值达到最大，即源的出流量或汇的入流量达到最大，每段弧都有对应的流量，而不是求网络中某个路径的流量。
把最大流算法想象成两个运输站之间运货，两个运输站之间有很多个中转站，每个中转站都有一个最大容量，站与站之间运货都有不同的运货量，而且中转站不会留货物，所以货物的总量一定等于源站的出货数或者汇站的进货数。最大流算法就是在不超过所有中转站的容量的情况下，求最大出货量/进货量以及所有中转站之间的运货量。
如下图所示，左边是容量，右边是流量，在如图所示的流中，流的值达到了最大，为13，也不存在增广路，所谓增广路就是一条从源到汇的路径，路径上的所有弧非饱和（正向）或非空（反向），即一条仍能增加流量的路。
为什么说增广路是一条仍能增加流量的路？其实不难理解，增广路的定义如上文，路径上的所有弧非饱和（正向）或非空（反向），反向弧的流量假设为n，实际上等价于为正向弧的流量为-n，因为n不能小于0，所以n=0的时候，反向弧的流量虽然达到了最小，但是把他当做正向弧的时候，流量却达到了最大。
对于一条路径而言，非饱和弧和非空弧都意味着该条路径的流量没有达到饱和。既然网络中存在一条没有达到饱和的路径，那么网络的流也没有达到最大。这就是当前流为最大流的充要条件，可用数学语言证明。
算法文字描述：
步骤0：将网络中所有弧流量全部置0
步骤1：将源的点流量设为无穷大，令u=s。
步骤2：标记 点
v
i
=
u
v_i=u
vi=u的所有未被标记的邻点
v
j
v_j
vj的点流量（BFS）。
标记方法：若u到邻点是正向弧，且流量小于容量，则点流量
Δ
(
v
j
)
Δ(v_j)
Δ(vj)取前点流量
Δ
(
v
i
)
Δ(v_i)
Δ(vi)和弧的容流量差值
C
i
j
−
F
i
j
C_{ij}-F_{ij}
Cij−Fij的较小者
若是反向弧连接，且流量大于0，则点流量
Δ
(
v
j
)
Δ(v_j)
Δ(vj)取前点流量
Δ
(
v
i
)
Δ(v_i)
Δ(vi)和弧流量
F
i
j
F_{ij}
Fij的较小者
步骤3：若标记到了汇则转步骤4，否则任选一个刚刚被标记的点设为
u
u
u，转步骤2，若刚刚没有标记任何点则算法结束。（步骤2由于会执行多次，刚刚表示步骤2最近一次执行时标记的点，即
v
i
v_i
vi的可被标记的邻点）
步骤4：从汇开始，依次回溯被标记的点，并将两点之间的弧加/减一个汇流量
Δ
(
t
)
Δ(t)
Δ(t)，正向则加，反向则减，回溯到源后，转步骤1。
算法符号描述：
步骤0： 设F是从源s到汇t的任意可行流，对任意
<
μ
,
v
>
=
<
v
i
,
v
j
>
∈
E
<μ,v>=<v_i,v_j>∈E
<μ,v>=<vi,vj>∈E，令
F
i
j
=
0
F_{ij}=0
Fij=0。//从零流开始。
步骤1： 对源
s
=
v
0
s=v_0
s=v0标记为
(
s
,
+
,
Δ
(
s
)
=
∞
)
，
S
=
｛
s
｝
，
U
=
｛
v
j
｝
,
j
=
0
,
1
,
2
,
⋯
,
n
；
μ
=
v
i
=
s
。
(s,+,Δ(s)=∞)，S=｛s｝，U=｛v_j｝,j=0,1,2,⋯,n；μ=v_i=s。
(s,+,Δ(s)=∞)，S=｛s｝，U=｛vj｝,j=0,1,2,⋯,n；μ=vi=s。(S表示已标记的顶点集，U未检查的顶点集，初始值为全体顶点。)
步骤2： 对
S
¯
S¯
S¯(S的补)中与
μ
=
v
i
μ=v_i
μ=vi的所有邻点
v
j
v_j
vj，有：
(1) 若
<
v
i
,
v
j
>
∈
E
，
且
F
i
j
<
C
i
j
<v_i,v_j>∈E，且F_{ij}<C_{ij}
<vi,vj>∈E，且Fij<Cij，则将
v
j
v_j
vj标记为
(
v
i
,
+
,
Δ
(
v
j
)
)
(v_i,+,Δ(v_j))
(vi,+,Δ(vj))，其中
Δ
(
v
j
)
=
m
i
n
｛
Δ
(
v
i
)
,
C
i
j
−
F
i
j
｝
，
S
=
S
∪
v
j
Δ(v_j)=min｛Δ(v_i),C_{ij}-F_{ij}｝，S=S∪{v_j}
Δ(vj)=min｛Δ(vi),Cij−Fij｝，S=S∪vj。
(2) 若
<
v
j
,
v
i
>
∈
E
<v_j,v_i>∈E
<vj,vi>∈E，且
F
i
j
>
0
F_{ij}>0
Fij>0，则将
v
j
v_j
vj标记为
(
v
i
,
−
,
Δ
(
v
j
)
)
(v_i,-,Δ(v_j))
(vi,−,Δ(vj))，其中
Δ
(
v
j
)
=
m
i
n
｛
Δ
(
v
i
)
,
F
i
j
｝
，
S
=
S
∪
v
j
Δ(v_j)=min｛Δ(v_i),F_{ij}｝，S=S∪{v_j}
Δ(vj)=min｛Δ(vi),Fij｝，S=S∪vj。
步骤3： 若
v
j
=
t
∈
S
v_j=t∈S
vj=t∈S，转步骤4，否则
v
j
≠
t
v_j≠t
vj=t，令
U
=
U
−
v
i
U=U-{v_i}
U=U−vi，若
S
∩
U
=
φ
S∩U=φ
S∩U=φ，则算法结束，当前流为最大流；否则若
S
∩
U
≠
φ
S∩U≠φ
S∩U=φ，任选
v
i
∈
S
∩
U
v_i∈S∩U
vi∈S∩U，转步骤2。（实际上，S∩U就是步骤2中刚刚被标记的点）
步骤4： 令
z
=
t
z=t
z=t。
步骤5： 若
z
z
z的标记为
(
g
,
+
,
Δ
(
z
)
)
(g,+,Δ(z))
(g,+,Δ(z))，则
F
(
<
g
,
z
>
)
=
F
(
<
g
,
z
>
)
+
Δ
(
z
)
F(<g,z>)=F(<g,z>)+Δ(z)
F(<g,z>)=F(<g,z>)+Δ(z)；
若z的标记为
(
g
,
−
,
Δ
(
z
)
)
(g,-,Δ(z))
(g,−,Δ(z))，则
F
(
<
z
,
g
>
)
=
F
(
<
z
,
g
>
)
−
Δ
(
z
)
F(<z,g>)=F(<z,g>)-Δ(z)
F(<z,g>)=F(<z,g>)−Δ(z)。
步骤6： 若
g
=
s
g=s
g=s，则取消所有点的标号，转步骤1，否则，令
z
=
g
z=g
z=g，转步骤5。
标记的意义：
(
v
i
,
+
,
Δ
(
v
j
)
)
(v_i,+,Δ(v_j ))
(vi,+,Δ(vj))表示点
v
i
v_i
vi经流量为
Δ
(
v
j
)
Δ(v_j)
Δ(vj)的正向弧到达点
v
j
v_j
vj
(
v
i
,
−
,
Δ
(
v
j
)
)
(v_i,-,Δ(v_j ))
(vi,−,Δ(vj))表示点
v
i
v_i
vi经流量为
Δ
(
v
j
)
Δ(v_j)
Δ(vj)的反向弧到达点
v
j
v_j
vj
符号描述可能不好理解，对照文字描述理解。
例子：（编辑太麻烦了，从word截的图）
欢迎讨论
