最大流问题的标号法 Ford-Fulkerson增广路径算法一、标号法的基本思路• 从一个可行流出发（若网络中没有给定F， 则可以设F是零流），经过标号过程和调整 过程1、标号过程• 在这个过程中，网络中的顶点或者是标号点（分为已检查 和未检查两种），或者是未标号点每个标号点的标号包 含两个部分第一个标号指明它的标号是从哪一个顶点得 到的（前驱指针），以便找出可改进路；第二个标号是为 确定可改进量a用的 • 标号过程开始，总先给Vs标上（0，+∞），这时Vs是标号而未检查的顶点，其余都是未标号点一般地，取一个标 号而未检查的顶点Vi，对于一切未标号点Vj： • （1）若在弧（vi,vj）上，fij0,则给vj标号（-vi,L(vj)）, L(vj)=min{L(vi),fji}这时顶点vj成为标号而未检查的顶点 • 在vi的全部相邻顶点都已标号后，vi成为标号而已检查过 的顶点重复上述步骤，一旦vt被标上号，表明得到一条 从vs到vt的可改进路P，转入调整过程；若所有标号都已检查过致使标号过程无法继续时，则算法结束这时的可 行流即最大流2、调整过程• 采用“倒向追踪”的方法，从vt开始，利用标号点的第一个标 号逐条弧地找出可改进路P，并以vt的第二个标号L(vt)作为 改进量a，改进P路上的流量。
• 例如设vt的第一个标号为vk（或-vk）,则弧(vk,vt)（或相应 的弧（vt,vk））是P上的弧接下来检查vk的第一标号， 直到查到vs为止这时被找出的弧就构成了可改进路P令 a=L（vt）调整改进P路上的流量：• 并去掉所有的标号，得到新的可行流F’={fij’},重新进入标号 过程，直至检查完所有标号为止s2143t(5,1)(3,3)(4,3)(2,2)(2,1)(5,3)(1,1)(1,1)(3,0)弧旁的数字是（cij,fij）二、标号法的算法流程• 1、数据结构：采用邻接表D存储 • Const maxn=xxx; • Type link=^dtype; • dtype=record • k:integer; {顶点序号} • f,c:integer; {流量，容量} • next,pre:link; {后向弧指针，前向弧 指针} • end; • Var d:array[1maxn] of link;• 可改进路的数据类型：将当前已标号点的可改进路存储在 数组path中，数据元素为可改进路上的结点，结点信息包 括标号（前驱结点指针p，当前可改进量d）和弧指针w: • Ptype=record • p,d:integer • w:link; • end; • Var path:array[1maxn] of ptype; • 队列：采用宽度优先搜索的方法求最大流。
• Var q:array[1maxn] of integer; • op,cl:integer; {队列指针}• 2、构造网络D的邻接表 • 每读入一条弧（u,v）的两个端点u,v及其容量c后，则在 D[u]的邻接表中插入流量为0，容量为c的前向弧（u，v） ；在D[v]对应的邻接表中插入流量为0，容量为0的后向弧 （v,u）这个过程可以用子过程insert(u,v,c)完成 • 构造过程： • 读定点数n，源点序号s和汇点序号t； • For i:=1 to n do d[i]:=nil; • While D网未读完 do • begin • 读入当前弧的两个端点u,v及其容量c； • insert(u,v,c)； • end;•Procedure insert(u,v,c:integer); •Var x:link; •Begin • x:=d[u]; •While (xv) do x:=x^.next; •If x0) then • begin • inc(op); q[op]:=x^.k; • path[x^.k].p:=u; path[x^.k].w:=x; • if path[u].d0 then •Begin • u:=t; a:=path[u].d; • repeat • path[u].w^.f:=path[u].w^.f+a; • path[u].w^.g^.f:=-path[u].w^.f; • u:=path[u].p; • until u=s; •End •Until path[t].p=0; •End; •4、输出最大流的流量 •Procedure answer; •Var I,tot:integer; • x:link; •Begin • tot:=0; • for i:=1 to n do • begin • x:=d[i]; • while x0 then 输出弧(i,x^.k)及其流量x^.f； • if (i=s) and (x^.f>0) then tot:=tot+x^.f; • x:=x^.next; • end; • end; •输出最大流量tot； •End;。