算法步骤如下：
STEP1：建造原网络G的一个分层网络L。
STEP2：用增广路算法计算L的最大流F，若在L中找不到增广路，算法结束。
SETP3：根据F更新G中的流f，转STEP1。
分层网络的构造算法：
STEP1：标号源节点s，M[s]＝0。
STEP2：调用广度优先遍历算法，执行一步遍历 *** 作，当前遍历的弧e=v1v2，令r＝G.u（e）－G.f（e）。
若r>0，则
（1）若M[v2]还没有遍历，则M[v2]=M[v1]+1，且将弧e加入到L中，容量L.u（e）＝r。
（2）若M[v2]已经遍历且M[v2]=M[v1]+1，则将边e加入到L中，容量L.u（e）＝r。
（3）否则L.u（e）＝0。
否则L.u（e）＝0。
重复本步直至G遍历完。其中的G.u(e)、G.f(e)、L.u(e)分别表示图G中弧e的容量上界和当前流量，图L中弧e的容量上界。
下附程序 （邻接表的程序，希望看得懂）
Program zw_dinicc
type
o=record
point,next,c:longint
end
Var
i,j,k,p,n,m,head,tail,s,t,tot,a1,a2,a3,tot1,a4:longint
h,l:array[1..55002]of longint
first:array[1..55002]of longint
e:array[1..310002] of o
procedure add(a,b,c:longint)
begin
e[tot1].point:=be[tot1].next:=first[a]e[tot1].c:=cfirst[a]:=tot1inc(tot1)
end
procedure init
var i,x,y,q:longint
begin
tot1:=2
readln(n,m)
for i:=m+2 to n+m+1 do
begin
read(a1)
add(i,n+m+2,a1)
add(n+m+2,i,0)
end
for i:=2 to m+1 do
begin
read(a1,a2,a3)
add(i,1+m+a1,65536000)add(1+m+a1,i,0)
add(i,1+m+a2,65536000)add(1+m+a2,i,0)
add(1,i,a3)add(i,1,0)
inc(j,a3)
end
n:=2+m+n
s:=1
t:=n
end
//以上为建边，用的是残量网络
procedure bfs｛构建分层图，从原点开始广搜｝
var
i,j,k,now:longint
begin
head:=1tail:=1 l[head]:=sfillchar(h,sizeof(h),127)h[s]:=0
while head<= tail do
begin
now:=l[head]inc(head)k:=first[now]
while k>0 do
begin
if (h[e[k].point]>n) and(e[k].c>0) then｛如果可以流，且该点未被访问｝
begin
h[e[k].point]:=h[now]+1
inc(tail)
l[tail]:=e[k].point
end
k:=e[k].next
end
end
end
function dfs(now,low:longint):longint｛根据分层图增广，low表示到now为止最多可增广流量｝
var
i,j,k,tmp:longint
begin
if now=t then exit(low)
dfs:=0 k:=first[now]
while k>0 do
begin
if (e[k].c>0) and (h[e[k].point]=h[now]+1) then｛如果在分层图中符合限制｝
begin
if e[k].c<low then tmp:=dfs(e[k].point,e[k].c)｛寻找可接受的最大流量｝
else tmp:=dfs(e[k].point,low)
if tmp=0 then h[e[k].point]:=maxlongint shr 1
dec(low,tmp)｛把可流量减去增广值｝
dec(e[k].c,tmp)
inc(e[k xor 1].c,tmp)
inc(dfs,tmp)
if low=0 then break｛若无法再增广，退出｝
end
k:=e[k].next
end
end
Procedure main
begin
bfs
while h[t]<n do｛如果在分层图中找得到汇点｝
begin
inc(tot,dfs(s,maxlongint))｛根据分层图增广｝
bfs｛根据新的流量构建分层图｝
end
end
Begin
assign(input,'profit.in')reset(input)
assign(output,'profit.out')rewrite(output)
init
main
writeln(j-tot)
close(input)close(output)
End.
看在本人手打这么多东西的份上，选我吧
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}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）