有关定义
前向弧和后向弧
在网络D(V, A) 中, 假使对连接发点vs和收点vt 的一条链P, 方向规定为从vs 到vt, 则当链P 中弧( vi,vj)
的方向与规定的方向统一时, 称弧( vi, vj) 为前向弧, 否则称为后向弧。不在这条链上的弧, 不定义前向弧和后向弧。
可扩充链
设{fij}为一可行流(如果为非负数), 假使存在从发点vs 到收点vt 的链P, 在链P 上, 下列两条同期满足, 则称P 为可扩充链:
①对于P 上的前向弧( vi,vj) 有fij
②对于P 上的后向弧( vi,vj) 有fij>0 。可扩充链P的费用
设对于可行流f 存在可扩充链P, 当以ε=1 调整f 而得到可行流f' 时, 两流的费用之差形成可扩充链p 的费用。其中P+和P- 分别表明p 上的前向弧和后向弧。 处理方法处理最小费用最大流困难，一般有两条渠道。一条渠道是先用最大流算法算出最大流，然后依据边费用，检查能否有机会在流量平衡的前提下通过调整边流量，使总费用得以降低？只要有这个或许，就执行如此的调整。调整后，得到一个新的最大流。
然后，在这个新流的基础上继续检查，调整。如此迭代下去，直至无调整或许，便得到最小费用最大流。这一思路的特点是维持困难的可行性（始终维持最大流），向最优推动。另一条处理渠道和前面介绍的最大流算法思路相相似，一般首先给出零流作为初始流。这个流的费用为零，诚然是最小费用的。然后寻求一条源点至汇点的增流链，但要求这条增流链务必是所有增流链中费用最小的一条。假使能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻求增流链增流。如此迭代下去，直至找不出增流链，这时的流即为最小费用最大流。这一算法思路的特点是维持解的最优性（每次得到的新流均为费用最小的流），而渐渐向可行解靠近（直至最大流时才是一个可行解）。
受于第二种算法和已介绍的最大流算法靠近，且算法中寻求最小费用增流链，可以转化为一个谋求源点至汇点的最短路径困难，所以这里介绍这一算法。
在这一算法中，为了谋求最小费用的增流链，对每一目前流，需建立伴随这一网络流的增流网络。比如图 1 网络G 是具有最小 费用的流，边旁参数为c(e) , f(e) , w(e)，而图 2 即为该网络流 的增流网络G′。增流网络的顶点和原网络相同。 按下方原则建 立增流网络的边：若G中边(u，v)流量未饱，即f(u,v) ＜ e(u,v)，则G ' 中建边(u,v)，赋权w ' (u,v)=w(u,v)；若G中边(u, v)已有流量，即f(u,v)〉0，则G′中建边(v,u)，赋权w′(v,u) =-w(u,v)。建立增流网络后，即可在此网络上求源点至汇点的最短路径，以此决定增流路径，然后在原网络上循此路径增流。这里，运用的依然是最大流算法的增流原理，唯务必选定最小费用的增流链增流。
计算中有一个困难需要处理。这就是增流网络G ′中有负权边，因此不能直接应用标号法来寻求x至y的最短路径，采取其它计算有负权边的网络最短路径的方法来寻求x至y的最短路径，将 大大减弱计算效率。为了依然采取标号法计算最短路径，在每次建立增流网络求得最短路径后,可将网络G的权w(e)做一次修正，使再建的增流网络不会显现负权边，并保证最短路径不至于所以而更改。下面介绍该种修改方法。 当流值为零，首次建增流网络求最短路径时，因无负权边，诚然可以采取标号法执行计算。为了使以后建立增流网络时不显现负权边，采取的办法是将 G中有流边（f(e)＞0）的权w(e)修正为0。为此， 每次在增流网络上求得最短路径后，下方式计算G中新的边权w " (u,v)：
w " (u,v)=L(u)-L(v)+w(u,v) (*)
式中 L(u),L(v) -- 计算G′的x至y最短路径时u和v的标号值。首次求最短径时假使(u,v)是增流路径上的边， 则据最短 路径算法一定有 L(v)=L(u)+w ' (u,v)=L(u)+w(u,v)， 代入(*)式必有
w″(u,v)=0。
假使(u,v)不是增流路径上的边，则一定有：
L(v)≤L(u)+w(u,v)， 代入(*)式则有 w(u,v)≥0。
可见首次修正w(e)后，对任一边，皆有w(e)≥0， 且有流 的边（增流链上的边），一定有w(e)=0。以后每次迭代计算，若 f(u,v)＞0，增流网络需建立(v,u)边，边权数w ' (v,u)=-w(u,v) =0，即不会再显现负权边。 另外，每次迭代计算用(*)式修正一切w(e)， 不难证明对每一条x至y的路径来说，其路径长度都同样增长L(x)-L(y)。所以，x至y的最短路径不会因对w(e)的修正而发生改变。
【计算步骤】
１. 对网络G=[V,E,C,W]，给出流值为零的初始流。
２. 作伴随这个流的增流网络G′=[V′,E′,W′]。 G′的顶点同G：V′=V。 若G中f(u,v)＜c(u,v)，则G′中建边(u,v)，w(u,v)=w(u,v)。 若G中f(u,v)＞0，则G′中建边(v,u)，w′(v,u)=-w(u,v)。
３. 若G′不存在x至y的路径，则G的流即为最小费用最大流， 停止计算；否则用标号法找出x至y的最短路径P。
４. 依据P，在G上增流： 对P的每条边(u,v)，若G存在(u,v)，则(u,v)增流；若G存在(v,u)，则(v,u)减流。增（减）流后，应保证对任一边有c(e)≥ f(e)≥0。
５. 依据计算最短路径时的各顶点的标号值L(v)，按下式修 改G一切边的权数w(e):
L(u)-L(v)+w(e)→w(e)。
６. 将新流看为初始流，转２。算法举例augment path
直译为“增广路”，其思想大差不差如下：
原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也就是容量）与E(G)相同。每次操作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。
我们很容易认为这个算法会深陷死循环，但实际上不是如此的。我们只需要注意到每次网络中由Source到Sink的流都增长了，若容量均为整数，则这个算法必然会终结。
寻求通路的时机可以用DFS，BFS最短路等算法。就这两者来看,BFS要比DFS快得多，但是编码量也会相应上一个数量级。
增广路方法可以处理最大流困难，但是它有一个不可避免的缺陷，就是在极端情形下每次只能将流扩大1（如果容量、流为整数），如此会产生性能上的很大困难，处理这个困难有一个复杂得多的算法，就是预推动算法。push label
直译为“预推动”算法。Push-Relabel
直译为压入与重标记算法
除了用各种方法在余下网络中持续找增广路(augmenting)的Ford-Fulkerson系的算法外，仍有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本操作有：压入，作用于一条边，将边的始点的预流尽或许多的压向终点；重标记，作用于一个点，将它的高度（也就是label）设为所有邻接点的高度的最小值加一。Push-Relabel系的算法广泛要比Ford-Fulkerson系的算法快，但是缺点是相对很难理解。
Relabel-to-Front运用一个链表保存溢出顶点，用Discharge操作持续使溢出顶点不再溢出。Discharge的操作过程是：若找不足可被压入的临边，则重标记，否则对临边压入，直至点不再溢出。算法的主过程是：首先将源点出发的所有边充满，然后将除源和汇外的所有顶点保存在一个链表里，从链表头开始执行Discharge，假使完成后顶点的高度有所增长，则将这个顶点置于链表的头部，对下一个顶点开始Discharge。
Relabel-to-Front算法的时间复杂度是O(V^3)，仍有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP，感觉它和Relabel-to-Front本质上没有区别，由于Relabel-to-Front每次前移的均为高度最高的顶点，所以也相当于每次选择最高的标号执行更新。仍有一个感觉也会很好达到的算法是运用队列维护溢出顶点，每次对pop出来的顶点discharge，显现了新的溢出顶点时入队。
Push-Relabel类的算法有一个名叫gap heuristic的优化，就是当存在一个整数0k的顶点v做更新，若它差于V+1就置为V+1。c++程序举例
#include
const long maxn=1000+10;
const long maxm=440000+100;
const long maxnum=100000000;
long n,m,s=0,tot=0,list[maxn],p[maxn],g[maxn],gg[maxn],dis[maxn];
bool mark[maxn];
struct node
{
long k,f,c,next,g;
}d[maxm<<1];
void insert(long u,long v,long c)
{
d[tot].k=v;
d[tot].f=0;
d[tot].c=c;
d[tot].next=g;
g=tot;
d[tot].g=tot+1;
tot++;
d[tot].k=u;
d[tot].f=0;
d[tot].c=0;
d[tot].next=g[v];
g[v]=tot;
d[tot].g=tot-1;
tot++;
}
void bfs()
{
long x,u,v,h,t;
for (long i=0;i
dis=0;
h=0;
t=1;
list[1]=0;
