相关定义
前向弧和后向弧
在网络D(V, A) 中, 如果对连接发点vs和收点vt 的一条链P, 方向规定为从vs 到vt, 则当链P 中弧( vi,vj)的方向与规定的方向一致时, 称弧( vi, vj) 为前向弧, 否则称为后向弧。不在这条链上的弧, 不定义前向弧和后向弧。
可扩充链
设{fij}为一可行流(假设为非负值), 如果存在从发点vs 到收点vt 的链P, 在链P 上, 下列两条同时满足, 则称P 为可扩充链:①对于P 上的前向弧( vi,vj) 有fij
可扩充链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的优化，就是当存在一个整数0
c++程序举例
#includeconst 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
h=0;
t=1;
list[1]=0;
-
相关文章
刘霆龙12.10黄金走势空头能否延续
元宇宙到底是什么？这十点看完就明白了
蚂蚁链“粉丝粒”，这会是全球最大NFT交
宁德时代股民年后户均亏损超百万
如何成为一名顶尖投资人？五点拿走不谢