zkw费用流+当前弧优化

zkw费用流+当前弧优化

 var

   o,v:array[..] of boolean;

   f,s,d,dis:array[..] of longint;

   next,p,c,w:array[-..] of longint;

   i,j,k,l,y,t,ss,tt,n,ans,imp,flow:longint;

 procedure link(i,j,k,l:longint);

 begin

   inc(t);

   next[t]:=d[i]; d[i]:=t; p[t]:=j; c[t]:=k; w[t]:=l;

   next[-t]:=d[j]; d[j]:=-t; p[-t]:=i; w[-t]:=-l;

 end;

 function dfs(i,flow:longint):longint;

 var j,k,l,min:longint;

 begin

   if i=tt then

   begin

     inc(ans,dis[i]*flow); exit(flow);

   end;

   k:=s[i]; j:=p[k]; dfs:=;

   o[i]:=true; v[i]:=true;

   while k<> do

   begin

     l:=dis[i]+w[k]-dis[j]; min:=flow;

     if c[k]<min then min:=c[k];

     if(min>)and(l<f[j])then f[j]:=l;

     if(min>)and(l=)and(not o[j])then

     begin

       l:=dfs(j,min);

       inc(dfs,l); dec(flow,l);

       dec(c[k],l); inc(c[-k],l);

     end;

     if flow= then break;

     s[i]:=next[s[i]];

     k:=s[i]; j:=p[k];

   end;

   o[i]:=false;

 end;

 begin

   build;

   repeat

     for i:=ss to tt do s[i]:=d[i];

     fillchar(v,sizeof(v),false);

     fillchar(f,sizeof(f),);

     inc(flow,dfs(ss, shl ));

     imp:= shl ;

     for i:=ss to tt do

     if(not v[i])and(f[i]<imp)then imp:=f[i];

     for i:=ss to tt do if not v[i] then inc(dis[i],imp);

   until imp= shl ;

   writeln(ans);

 end.

PASCAL

 #include<bits/stdc++.h>

 using namespace std;

 const int INF=;

 int o[],v[],f[],c[],s[],dis[];

 int b[],p[],d[],w[];

 int j,k,ss,tt,n,ans,imp,flow,cnt;

 void link(int i,int j,int k,int l)

 {

     cnt++; b[cnt]=c[i]; c[i]=cnt; p[cnt]=j; d[cnt]=k; w[cnt]=l;

     cnt++; b[cnt]=c[j]; c[j]=cnt; p[cnt]=i; d[cnt]=; w[cnt]=-l;

 }

 int dfs(int x,int flow)

 {

     if(x==tt){ ans+=dis[x]*flow; return flow; }

     int ans2=; o[x]=; v[x]=;

     for(int i=s[x];i;i=b[i])

     {

         int j=p[i]; int l=dis[x]+w[i]-dis[j]; int mi=min(flow,d[i]);

         if((mi>)and(l<f[j]))f[j]=l;

         if((mi>)and(l==)and(!o[j]))

         {

             l=dfs(j,mi);

             ans2+=l; flow-=l; d[i]-=l; d[i^]+=l;

         }

         if(flow==)break; s[x]=b[s[x]];

     }

     o[x]=; return ans2;

 }

 int main()

 {

     cnt=; build;

     while()

     {

         for(int i=ss;i<=tt;i++)s[i]=c[i];

         memset(v,,sizeof(v)); for(int i=ss;i<=tt;i++)f[i]=INF;

         flow+=dfs(ss,INF); imp=INF;

         for(int i=ss;i<=tt;i++)if((!v[i])and(f[i]<imp))imp=f[i];

         if(imp==INF)break;

         for(int i=ss;i<=tt;i++)if(!v[i])dis[i]+=imp;

     }

     printf("%d %d\n",flow,ans);

 }

C++