算法模板——Dinic最小费用最大流

实现功能：输入M,N,S,T；接下来M行输入M条弧的信息（包括起点，终点，流量，单位费用）；实现功能是求出以S为源点，T为汇点的网络最大流的最小费用

其实相当的像Dinic最大流呐= =

还是spfa处理出最短路径（注意，这次是最短路径，所以时空复杂度将有所提高，害得我都开循环队列了TT），然后顺着最短路径顺藤摸瓜找回去，求出流大小和最小的费用，然后，没有然后了，程序还是一样的好懂么么哒（HansBug:感觉Dinic算法真心超级喜感，为啥我之前就没发现呢= =，还有鸣谢wnjxyk神犇提供的C++模板么么哒 Wnjxyk：^_^）

（本程序为BZOJ1927的AC程序，模板题么么哒,还有其实感觉spfa函数里面每次清空e数组貌似不是很必要，但还是图个安心写下吧）

 const maxl=;

 type

     point=^node;

     node=record

                g,w,f:longint;

                next,anti:point;

     end;

 var

    a,e:array[..] of point;

    i,j,k,l,m,n,s,t,ans,flow:longint;

    c,g:array[..] of longint;

    d:array[..maxl] of longint;

 function min(x,y:longint):longint;

          begin

               if x<y then min:=x else min:=y;

          end;

 procedure swap(var x,y:longint);

           var z:longint;

           begin

                z:=x;x:=y;y:=z;

           end;

 procedure add(x,y,z,t:longint);

           var p:point;

           begin

                new(p);p^.g:=y;p^.w:=z;p^.f:=t;p^.next:=a[x];a[x]:=p;

                new(p);p^.g:=x;p^.w:=;p^.f:=-t;p^.next:=a[y];a[Y]:=p;

                a[x]^.anti:=a[y];a[y]^.anti:=a[x];

           end;

 function spfa:boolean;     //神(dou)奇(bi)的最短路径预处理

          var f,r:longint;p:point;

          begin

               for i:=s to t do c[i]:=maxlongint;

               for i:=s to t do e[i]:=nil;

               d[]:=s;f:=;r:=;g[s]:=;c[s]:=;

               while f<>r do

                     begin

                          p:=a[d[f]];

                          while p<>nil do

                                begin

                                     if (p^.w<>) and (c[p^.g]>(c[d[f]]+p^.f)) then

                                        begin

                                             c[p^.g]:=c[d[f]]+p^.f;

                                             e[p^.g]:=p;

                                             if g[p^.g]= then

                                                begin

                                                     g[p^.g]:=;

                                                     d[r]:=p^.g;r:=(r mod maxl)+;

                                                end;

                                        end;

                                     p:=p^.next;

                                end;

                          g[d[f]]:=;f:=(f mod maxl)+;

                     end;

               exit(c[t]<>maxlongint);

          end;

 procedure calc;

           begin

                l:=maxlongint;

                i:=t;

                while i<>s do

                      begin

                           l:=min(l,e[i]^.w);

                           i:=e[i]^.anti^.g;   //当前弧的反向弧所指向的点就是你要回到的点^_^

                      end;

                i:=t;inc(flow,l);

                while i<>s do

                      begin

                           if e[i]^.w<>maxlongint then dec(e[i]^.w,l);

                           if e[i]^.anti^.w<>maxlongint then inc(e[i]^.anti^.w,l);

                           inc(ans,e[i]^.f*l);

                           i:=e[i]^.anti^.g;

                      end;

           end;

 begin

      readln(n,m);s:=;t:=*n+;

      for s:= to t do a[i]:=nil;

      for i:= to n do

          begin

               read(l);

               add(,i,,);

               add(i+n,t,,);

               add(,i+n,,l);

          end;

      readln;

      for i:= to m do

          begin

               readln(j,k,l);

               if j>k then swap(j,k);

               add(j,k+n,,l);

          end;

      flow:=;ans:=; //flow表示最大流；ans表示最小费用

      while spfa do calc;

      writeln(ans);

      readln;

 end.

巴特西

算法模板——Dinic最小费用最大流

最新文章

热门文章