网络流是一类应用非常广泛的算法，但它们的难度相对其他算法来说也较大。而最大流，是网络流其他算法的基础。
网络流的基本概念
先来看一个实例。
5-1
现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下图：
每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？
这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。
若有向图G=(V,E)满足下列条件：
1、 有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。
2、 有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。
3、 每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。
则称之为网络流图，记为G = (V, E, C)
譬如图5-1就是一个网络流图。
1．可行流
对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
1、 每一条弧(i,j)有fij≤cij。
2、 除源点S和汇点T以外的所有的点vi，恒有：
该等式说明中间点vi的流量守恒，输入与输出量相等。
3、 对于源点S和汇点T有：
这里V(f)表示该可行流f的流量。
例如对图5-1而言，它的一个可行流如下：
流量V(f) = 5。
2．可改进路
给定一个可行流f=。若fij = cij，称<vi, vj>为饱和弧；否则称<vi, vj>为非饱和弧。若fij = 0，称<vi, vj>为零流弧；否则称<vi, vj>为非零流弧。
定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。
譬如在图5-1中，P = (S, V1, V2, V3, V4, T)，那么
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
给定一个可行流f，P是从S到T的一条道路，如果满足：
那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。具体方法下一节会重点介绍，此不赘述。
3．割切
要解决网络最大流问题，必须先学习割切的概念和有关知识。
G = (V, E, C)是已知的网络流图，设U是V的一个子集，W = V/U，满足S U，T W。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。
对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：
例如图5-1中，令U = {S, V1}，则W = {V2, V3, V4, T}，那么
C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4>=8+4+4+1=17
定理：对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有：V(f) ≤ C(U, W)。
通俗简明的讲：“最大流小于等于最小割”。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。
下面我们给出证明。
网络流、可改进路、割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。
二、求最大流
何谓最大流？首先它必须是一个可行流；其次，它的流量必须达到最大。这样的流就称为最大流。譬如对图5-1而言，它的最大流如下：
下面探讨如何求得最大流。
在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则”。
对可改进路P上的弧<vi, vj>，分为两种情况讨论：
第一种情况：<vi, vj>∈P+，可以令fij增加一个常数delta。必须满足fij + delta ≤ cij，即delta ≤ cij – fij。
第二种情况：<vi, vj>∈P-，可以令fij减少一个常数delta。必须满足fij - delta ≥ 0，即delta ≤ fij
根据以上分析可以得出delta的计算公式：
因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，所以delta > 0。
容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”（即输入量等于输出量），又可以使得总的流量有所增加（因为delta > 0）。
因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在的问题是：倘若在f中找不到可改进路，是不是f就一定是最大流呢？
答案是肯定的。下面我们给出证明。
定理1 可行流f是最大流的充分必要条件是：f中不存在可改进路。
证明：
首先证明必要性：已知最大流f，求证f中不存在可改进路。
若最大流f中存在可改进路P，那么可以根据一定规则（详见上文）修改P中弧的流量。可以将f的流量放大，这与f是最大流矛盾。故必要性得证。
再证明充分性：已知流f，并且f中不存在可改进路，求证f是最大流。
我们定义顶点集合U, W如下：
（a） S∈U，
（b） 若x∈U，且fxy<cxy，则y∈U;
若x∈U，且fyx>0，则y∈U。
（这实际上就是可改进路的构造规则）
（c） W = V / U。
由于f中不存在可改进路，所以T∈W；又S∈U，所以U、W是一个割切（U, W）。
按照U的定义，若x∈U，y∈W，则fxy = cxy。若x∈W，y∈U，则fxy = 0。
所以，
又因 v(f)≤C(U,W)
所以f是最大流。得证。
根据充分性证明中的有关结论，我们可以得到另外一条重要定理：
最大流最小割定理：最大流等于最小割，即max V(f) = min C(U, W)。
至此，我们可以轻松设计出求最大流的算法：
step 1. 令所有弧的流量为0，从而构造一个流量为0的可行流f（称作零流）。
step 2. 若f中找不到可改进路则转step 5；否则找到任意一条可改进路P。
step 3. 根据P求delta。
step 4. 以delta为改进量，更新可行流f。转step 2。
step 5. 算法结束。此时的f即为最大流。
我写了一个最大流算法的模板，希望对大家有所帮助，但由于水平所限，算法中可能存在一些不严谨的地方，欢迎大家提出宝贵意见和建议，代码如下:
#include <iostream>
#include <memory.h>
#include <math.h>
using namespace std;
struct sign
{
int l,p;
};
struct graph
{
int f,c;
};
sign lt[101];
graph map[101][101];
int n,m,s,t,temp;
int check()
{
int i;
i=1;
while((i<=n)&&(!(lt[i].l!=0&<[i].p==0)))
i++;
if(i>n)
return 0;
else
return i;
}
void init()
{
int i,x,y,z;
memset(lt,0,sizeof(lt));
memset(map,0,sizeof(map));
cin>>n>>m>>s>>t;
for(i=1;i<=m;i++)
{
cin>>x>>y>>z;
map[x][y].c=z;
}
}
bool ford()
{
int i,j,pre,x;
memset(lt,0,sizeof(lt));
lt[s].l=s;
while(lt[t].l==0)
{
i=check();
if(i==0)
return false;
for(j=1;j<=n;j++)
if((lt[j].l==0)&&(map[i][j].c>0||map[j][i].c>0))
{
if(map[i][j].f<map[i][j].c)
lt[j].l=i;
if(map[j][i].f>0)
lt[j].l=-i;
}
lt[i].p=1;
}
i=t;
temp=65535;
while(i!=s)
{
pre=abs(lt[i].l);
if(lt[i].l>0)
x=map[pre][i].c-map[pre][i].f;
if(lt[i].l<0)
x=map[i][abs(pre)].f;
if(x<temp)
temp=x;
i=pre;
}
return true;
}
void fulkerson()
{
int i,pre;
i=t;
while(i!=s)
{
pre=abs(lt[i].l);
if(lt[i].l>0)
map[pre][i].f+=temp;
if(lt[i].l<0)
map[i][pre].f-=temp;
i=pre;
}
}
void print()
{
int i,max=0;
for(i=1;i<=n;i++)
if(map[i][t].f>0)
max+=map[i][t].f;
cout<<max<<endl;
}
int main()
{
init();
while(ford())
fulkerson();
print();
return 0;
}