现在的位置: 首页 > 综合 > 正文

网络流

2014年04月05日 ⁄ 综合 ⁄ 共 2186字 ⁄ 字号 评论关闭

       做到USACO4.2.1,我猛然发现这是最大流。而以前我对网络流一直有种莫名的畏惧,所以只懂一点理论而不会代码。今天我就打算看一些代码来初步领会这个强大的算法。以下是我搜集的两个比较易懂的代码:

最大容量增广路算法

每次找一条容量最大的增广路来增广,找的过程类似Dijkstra,实现起来相当简单。

procedure findstream;{寻找增广路径,每次找的都是流量最大的那一条}
    var
      flag:array[1..maxn]of boolean;
      have,pr:array[1..maxn]of longint;{have为能扩展此点的最大的流值 pr为此点前驱}
      mi,i,max:longint;
    begin
      fillchar(flag,sizeof(flag),false);
      fillchar(have,sizeof(have),0);
      have[s]:=2000000000;pr[s]:=0;
      while true do{用死循环在里面跳出}
        begin
          max:=0;mi:=-1;
          for i:=1 to n do
            if (not flag[i])and(have[i]>max) then{找当前能扩展出的最大流值,注意:必须是没有被标记过的}
              begin max:=have[i];mi:=i;end;
          if mi=-1 then exit;{找不到了,最大流值都为0,根本找不到了,应当退出}
          if mi=t then break;{推到终点了,应该退出循环}
          flag[mi]:=true;{标记当前点,免得以后重复访问}
          for i:=1 to n do
            if (not flag[i])and(map[mi,i]>=have[i])and(max>=have[i]) then
              {做出调整,更新推到每一点的流值,更新点必须满足未被标记,并且刚刚标记的点能推到此点并更新此点,因此推倒mi的流要比i的大、mi->i这条边的流量要比原扩展到i的流(即have[i])也要大,不然无法从mi推到i}
              begin
                have[i]:=map[mi,i];
                if have[i]>max then have[i]:=max;
               {have[i]取map[mi,i]与have[mi](max)中较小者}
                pr[i]:=mi;{重新定义i的前驱}
              end;
        end;
      f:=have[t];i:=t;
      while pr[i]<>0 do{沿着增广路径倒着回去,把每一条边cut掉已经占用的那一部分,并把相应的反向弧的容量增加}
        begin
          dec(map[pr[i],i],f);
          inc(map[i,pr[i]],f);
          i:=pr[i];
        end;
    end;

Edmonds-Karp,最短路增广算法的BFS实现

procedure calc;
  var
    q:array[1..maxn]of longint;
    open,closed,i,j,v,d,m:longint;
  begin
    repeat
      fillchar(information,sizeof(information),0);
      information[s].have:=max;information[s].father:=s;{初始标记,便于以后操作}
      open:=0;closed:=1;q[closed]:=s;{初始队列,用BFS实现寻找最短路}
      while (open<closed)and(information[t].father=0) do
        begin
          inc(open);i:=q[open];
          for j:=1 to vetex[i,0] do{检查所有边}
          if (information[vetex[i,j]].father=0)
             and((map[i,vetex[i,j]].c<>0)or(map[vetex[i,j],i].c<>0)) then
            begin
              v:=vetex[i,j];
              if (map[i,v].f<map[i,v].c) then{还有容量剩余}
                begin
                  information[v].father:=i;
                  information[v].have:=min(information[i].have,map[i,v].c-map[i,v].f);
                  inc(closed);q[closed]:=v;
                end;
              if (map[v,i].f>0) then{存在反向边,容许流量通过}
                begin
                  information[v].father:=-i;
                  information[v].have:=min(information[i].have,map[v,i].f);
                  inc(closed);q[closed]:=v;
                end;
            end;
        end;
      if information[t].father=0 then break;{无法增广}
      d:=information[t].have;
      m:=t;inc(total,d);
      repeat{进行增广}
        j:=m;m:=abs(information[j].father);
        if information[j].father<0 then map[j,m].f:=map[j,m].f-d;
        if information[j].father>0 then map[m,j].f:=map[m,j].f+d;
      until m=s;
    until false;
    writeln(total);
    close(input);close(output);
  end;

抱歉!评论已关闭.