相关定义

前向弧和后向弧

　　在网络D(V, A) 中, 如果对连接发点vs和收点vt 的一条链P, 方向规定为从vs 到vt, 则当链P 中弧( vi,vj) 　　的方向与规定的方向一致时, 称弧( vi, vj) 为前向弧, 否则称为后向弧。不在这条链上的弧, 不定义前向弧和后向弧。

可扩充链

　　设{fij}为一可行流(假设为非负值), 如果存在从发点vs 到收点vt 的链P, 在链P 上, 下列两条同时满足, 则称P 为可扩充链: 　　①对于P 上的前向弧( vi,vj) 有fij<cij。 　　②对于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点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。 　　我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由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的优化，就是当存在一个整数0<k<V，没有任何顶点满足h[v]=k时，对所有h[v]>k的顶点v做更新，若它小于V+1就置为V+1。

c++程序举例

　　#include<cstdio> 　　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<n;i++) 　　dis=0; 　　h=0; 　　t=1; 　　list[1]=0;