网络流的最大流算法

1、augment path，直译为“增广路径”，其思想大致如下：

原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也就是容量）与E(G)相同。每次 *** 作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。

我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由Source到Sink的流都增加了，若容量都是整数，则这个算法必然会结束。

寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。

增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1（假设容量、流为整数），这样会造成性能上的很大问题，解决这个问题有一个复杂得多的算法，就是预推进算法。

2、push label，直译为“预推进”算法。

3、压入与重标记(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。

cpp程序: #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define inf 0x7fffffffusingnamespace stdint tt,kaseint nn,mint H[45],X[1004],P[1004],flow[1004],tot,cap[1005]int d[45]int S,Tvoid add(int x,int y,int z){P[++tot]=yX[tot]=H[x]H[x]=totflow[tot]=zcap[tot]=flow[tot]}queue<int> qbool bfs(){memset(d,0,sizeof(d))d[S]=1 int xq.push(S)while(!q.empty()){x=q.front()q.pop()for(int i=H[x]ii=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1q.push(P[i])}}}returnd[T]}int dfs(int x,int a){if(x==T||a==0)return aint f=a,tmpfor(int i=H[x]ii=X[i]){if(flow[i]>0&&d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a))flow[i]-=tmpa-=tmpflow[i^1]+=tmpif(!a)break}}if(f==a)d[x]=-1return f-a}int Dinic(){int f=0while(bfs())f+=dfs(S,inf)return f}int main(){/**输入过程省略**/int maxflow=Dinic()printf(%d\n,maxflow)return 0}

可以看一下百度百科：

http://baike.baidu.com/view/165435.html?wtp=tt

或者这个（图片复制不下来）：

5.1 基本概念

在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。

1.问题描述 如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。

图5-1 图5-2

2.网络与网络流

给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。

3.可行流与最大流

在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：

(1)容量约束：0≤fij≤cij，(vi,vj)∈E，

(2)守恒条件

对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）

的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。

网络N中流值最大的流f*称为N的最大流。

4.可增广路径

所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。

设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：

(1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤fij<cij

(2)在p上的所有后向弧(vi←vj)都是非零弧，即0<fij≤cij

则称p为(关于可行流f的)一条可增广路径。

5.最大流定理

当且仅当不存在关于f*的增广路径，可行流f*为最大流。

5. 2 最大流算法

算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。

1.寻求最大流的标号法(Ford,Fulkerson)

从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。

(1)标号过程

在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个 部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。

标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。

取一个标号而未检查的点vi，对于一切未标号的点vj：

A．对于弧(vi，vj)，若fij<cij，则给vj标号(vi，0)，这时，vj点成为标号而未检查的点。

B．对于弧(vi，vj)，若fji>0，则给vj标号(-vi，0)，这时，vj点成为标号而未检查的点。

于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。

若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。

(2)调整过程

从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或 相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一 标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：

Q=min{min(cij-fij)，minf*ij}

对流f进行如下的修改：

f'ij = fij+Q (vi，vj)∈ P的前向弧的集合

f'ij = fij-Q (vi，vj)∈ P的后向弧的集合

f'ij = f*ij (vi，vj)不属于P的集合

接着，清除所有标号，对新的可行流f’，重新进入标号过程。

例1:下图表示一个公路网,V1是某原材料产地,V6表示港口码头,每段路的通过能力(容量)如图上的各边上的数据,找一运输方案,使运输到码头的原材料最多?

程序如下:

Program Max_Stream

Const Maxn=20

type

nettype=record

C,F:integer

end

nodetype=record

L,P:integer

end

var

Lt:array[0..maxn] of nodetype

G:Array[0..Maxn,0..Maxn] of Nettype

N,S,T:integer

F:Text

Procedure Init{初始化过程，读人有向图，并设置流为0}

Var Fn :String

I,J :Integer

Begin

Write( 'Graph File = ' )Readln(Fn)

Assign(F,Fn)

Reset(F)

Readln(F,N)

Fillchar(G,Sizeof(G) ,0)

Fillchar(Lt,Sizeof(Lt),0)

For I:=1 To N Do

For J:=1 To N Do Read(F,G[I,J].C)

Close(F)

End

Function Find: Integer{寻找已经标号未检查的顶点}

Var I: Integer

Begin

I:=1

While (I<=N) And Not((Lt[I].L<>0)And(Lt[I].P=0)) Do Inc(I)

If I>N Then Find:= 0 Else Find:= I

End

Function Ford(Var A: Integer):Boolean

Var {用标号法找增广路径，并求修改量A}

I,J,M,X:Integer

Begin

Ford:=True

Fillchar(Lt,Sizeof(Lt),0)

Lt[S].L:=S

Repeat

I:= Find

If i=0 Then Exit

For J:=1 To N Do

If (Lt[J].L= 0)And((G[I,J].C<>0)or(G[J,I].C<>0)) Then

Begin

if (G[I,J].F<G[I,J].C) Then Lt[J].L:= I

If (G[J,I].F>0) Then Lt[J].L:=-I

End

Lt[I].P:=1

Until (Lt[T].L<>0)

M:=TA:=Maxint

Repeat

J:=MM:=Abs(Lt[J].L)

If Lt[J].L<0 Then X:= G[J,M].F

If Lt[J].L>0 Then X:= G[M,J].C- G[M,J].F

If X<A Then A:= X

Until M= S

Ford:=False

End

Procedure Change(A: Integer){调整过程}

Var M, J: Integer

Begin

M:= T

Repeat

J:=MM:=Abs(Lt[J].L)

If Lt[J].L<0 Then G[J,M].F:=G[J,M].F-A

If Lt[J].L>0 Then G[M,J].F:=G[M,j].F+A

Until M=S

End

Procedure Print{打印最大流及其方案}

VAR

I ,J: Integer

Max: integer

Begin

Max:=0

For I:=1 To N DO

Begin

If G[I,T].F<>0 Then Max:= Max + G[I,T].F

For J:= 1 To N Do

If G[I,J].F<>0 Then Writeln( I, '->' ,J,' ' ,G[I,J].F)

End

Writeln('The Max Stream=',Max)

End

Procedure Process{求最大流的主过程}

Var Del:Integer

Success:Boolean

Begin

S:=1T:=N

Repeat

Success:=Ford(Del)

If Success Then Print

Else Change(Del)

Until Success

End

Begin {Main Program}

Init

Process

End.

测试数据文件(zdl.txt)如下:

6

0 3 5 0 0 0

0 0 1 4 0 0

0 0 0 0 2 0

0 0 0 0 0 5

0 1 0 3 0 2

0 0 0 0 0 0

运行结果如下:

Graph File=zdl.txt

1->2 3

1->3 2

2->4 3

3->5 2

4->6 3

5->6 2

The Max Stream=5

5.3最小费用最大流及算法

上面的网络，可看作为辅送一般货物的运输网络，此时，最大流问题仅表明运输网络运输货物的能力，但没有考虑运送货物的费用。在实际问题中，运送同样数量货物的运输方案可能有多个，因此从中找一个输出费用最小的的方案是一个很重要的问题，这就是最小代价流所要讨论的内容。

1.最小费用最大流问题的模型

给定网络N=(V，E，c，w，s，t)，每一弧(vi,vj)属于E上，除了已给容量cij外，还给了一个单位流量的费用w(vi,vj)≥O(简记为wij)。所谓最小费用最大流问题就是要求一个最大流f，使得流的总输送费用取最小值。

W(f)=∑wijfij

2.用对偶法解最小费用最大流问题

定义：已知网络N=(V，E，c，w，s，t)，f是N上的一个可行流，p为vs到vt(关于流f)的可增广路径，称W(p)=∑wij（p+）-∑wij（p-）为路径p的费用。

若p*是从vs到vt所有可增广路径中费用最小的路径，则称p*为最小费用可增广路径。

定理：若f是流量为v(f)的最小费用流，p是关于f的从vs到vt的一条最小费用可增广路径，则f经过p调整流量Q得到新的可行流f’(记为f’=f+Q)，一定是流量为v(f)+Q的可行流中的最小费用流。

3.对偶法的基本思路

①取f={0}

②寻找从vs到vt的一条最小费用可增广路径p。

若不存在p，则f为N中的最小费用最大流，算法结束。

若存在p，则用求最大流的方法将f调整成f*，使v(f*)=v(f)+Q，并将f*赋值给f，转②。

4.迭代法求最小费用可增广路径

在前一节中，我们已经知道了最大流的求法。在最小费用最大流的求解中，每次要找一条最小费用的增广路径，这也是与最大流求法唯一不同之处。于是，对于求最小费用最大流问题余下的问题是怎样寻求关于f的最小费用增广路径p。为此，我们构造一个赋权有向图b(f)，它的顶点是原网络N中的顶点，而把N中每一条弧(vi，vj)变成两个相反方向的弧(vi，vj)和(vj，vi)。定义w(f)中的弧的权如下：

如果(fij<cij)，则bij=wij ；如果(fij=cij)，则bij=+oo

如果(fij>0)，则bji=-wij ；如果(fij=cij)，则bji=+oo

于是在网络N中找关于f的最小费用增广路径就等价于在赋权有向图b(f)中，寻求从vs到vt的最短路径。求最短路有三种经典算法，它们分别是Dijkstra算法、Floyd算法和迭代算法(ford算法）。由于在本问题中，赋权有向图b(f)中存在负权，故我们只能用后两种方法求最短路，其中对于本问题最高效的算法是迭代算法。为了程序的实现方便，我们只要对原网络做适当的调整。将原网络中的每条弧(vi，vj)变成两条相反的弧：

前向弧(vi,vj)，其容量cij和费用wij不变，流量为fij；

后向弧(vj,vi)，其容量0和费用-wij，流量为-fij。

事实上，对于原网络的数据结构中，这些单元已存在，在用标号法求最大流时是闲置的。这样我们就不必产生关于流f的有向图b(f)。同时对判断(vi,vj)的流量可否改时，可以统一为判断是否“fij<cij”。因为对于后向弧(vj，vi)，若fij>0，则fji=-fij<0=cji。

例2：求输送量最大且费用最小的运输方案？

如下图是一公路网，v1是仓库所在地（物资的起点），v5是某一工地（物资的终点）每条弧旁的两个数字分别表示某一时间内通过该段路的最多吨数和每吨物资通过该段路的费用。

程序如下：

{最小费用最大流参考程序}

program Maxflow_With_MinCost

const

name1='flow.in'

name2='flow.out'

maxN=100{最多顶点数}

type

Tbest=record {数组的结构}

value,fa:integer

end{到源点的最短距离，父辈}

Nettype=record

{网络邻接矩阵类型}

c,w,f:integer

{弧的容量，单位通过量费用，流量}

end

var

Net:array[1..maxN,1..maxN] Of Nettype

{网络N的邻接矩阵}

n,s,t:integer{顶点数，源点、汇点的编号}

Minw:integer{最小总费用}

best:array[1..maxN] of Tbest{求最短路时用的数组}

procedure Init{数据读人}

var inf:text

a,b,c,d:integer

begin

fillchar(Net,sizeof(Net),0)

Minw:=0

assign(inf,name1)

reset(inf)

readln(inf,n)

s:=1t:=n{源点为1，汇点n}

repeat

readln(inf,a,b,c,d)

if a+b+c+d>0 then

begin

Net[a,b].c:=c{给弧(a,b)赋容量c}

Net[b,a].c:=0{给相反弧(b,a)赋容量0}

Net[a,b].w:=d{给弧(a,b)赋费用d}

Net[b,a].w:=-d{给相反孤(b，a)赋费用-d}

end

until a+b+c+d=0

close(inf)

end

function Find_Path:boolean

{求最小费用增广路函数,若best[t].value<>MaxInt,

则找到增广路，函数返回true，否则返回false}

var Quit:Boolean

i,j:Integer

begin

for i:=1 to n do best[i].value:=Maxintbest[s].value:=0

{寻求最小费用增广路径前，给best数组赋初值}

repeat

Quit:=True

for i:=1 to n do

if best[i].Value <Maxint then

for j:=1 to n do

if (Net[i,j].f <Net[i,j].c) and

(best[i].value + Net[i,j].w <

best[j].value) then

begin

best[j].value:=best[i].value + Net[i,j].w

best[j].fa := i

Quit:= False

end

until Quit

if best[t].value<Maxint then find_path:=true else find_path:=false

end

procedure Add_Path

var i,j: integer

begin

i:= t

while i <>s do

begin

j := best[i].fa

inc(Net[j,i].f){增广路是弧的数量修改，增量1}

Net[i,j].f:=-Net[j,i].f{给对应相反弧的流量赋值-f}

i:=j

end

inc(Minw,best[t].value){修改最小总费用的值}

end

procedure Out{输出最小费用最大流的费用及方案}

var ouf: text

i,j: integer

begin

assign(ouf,name2)

rewrite(ouf)

writeln(ouf,'Min w = ',Minw)

for i := 1 to n do

for j:= 1 to n do

if Net[i,j].f >0 then

writeln(ouf,i, ' ->',j,': ',

Net[i,j].w,'*',Net[i,j].f)

close(ouf)

end

Begin {主程序}

Init

while Find_Path do Add_Path

{当找到最小费用增广路，修改流}

Out

end.

flow.in如下：

5

1 2 10 4

1 3 8 1

2 4 2 6

2 5 7 1

3 2 5 2

3 4 10 3

4 5 4 2

0 0 0 0

运行结果flow.out如下：

Min w = 55

1 ->2: 4*3

1 ->3: 1*8

2 ->5: 1*7

3 ->2: 2*4

3 ->4: 3*4

4 ->5: 2*4

让程序对输入的字符进行检测：

if(开头不为0)则输出十进制

else//开头第一个为0

{

if(0后面的为x)则是十六进制

else 为八进制

}

---