POJ 2516(最小费用最大流)

内容目录

一开始居然忘添反向边……

Program P2516;
const
   maxn=100;
   maxm=100;
   maxk=100;
var
   n,m,k,i,j,l,maxflow:longint;
   need,prod:array[1..maxn,1..maxk] of longint;
   needk,prodk:array[1..maxk] of longint;
   fee:array[1..maxk,1..maxn,1..maxm] of longint;

   cost,map,f:array[0..200,0..200] of longint;

   b:array[0..200] of boolean;
   d,pre:array[0..200] of longint;
   q:array[1..500000] of longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure spfa;
var
   i,j,l,h,t,now:longint;
begin
   fillchar(d,sizeof(d),127);
   fillchar(b,sizeof(b),false);
   fillchar(pre,sizeof(pre),0);
   d[0]:=0;
   b[0]:=true;
   q[1]:=0;
   h:=1;t:=1;
   while h<=t do
   begin
      now:=q[h];
      for i:=0 to n+m+1 do
         if (map[now,i]-f[now,i]>0) then
            if (d[now]+cost[now,i]<d[i]) then
            begin
               d[i]:=d[now]+cost[now,i];
               pre[i]:=now;
               if not(b[i]) then
               begin
                  b[i]:=true;
                  inc(t);
                  q[t]:=i;
               end;
            end;


      b[now]:=false;
      inc(h);
   end;


end;
function hllp:longint;
var
   i,j,l,flow,totalflow,p:longint;
   totalcost,nowcost:longint;
begin
   hllp:=0;
   totalflow:=0;
   totalcost:=0;
   while (true) do
   begin
      spfa;
      if d[n+m+1]=2139062143 then exit(totalcost);
      flow:=maxlongint;
      i:=n+m+1;

      repeat
         flow:=min(flow,map[pre[i],i]-f[pre[i],i]);
         i:=pre[i];
      until i=0;

      nowcost:=0;
      i:=n+m+1;
      repeat
         inc(f[pre[i],i],flow);
         f[i,pre[i]]:=-f[pre[i],i];
         inc(nowcost,cost[pre[i],i]);
         i:=pre[i];
      until i=0;
      inc(totalcost,nowcost*flow);
   end;
end;
function main:longint;
var
   i,j,l,s,t:longint;
begin
   main:=0;
   for i:=1 to k do if prodk[i]<needk[i] then exit(-1);
   for i:=1 to k do
   begin
      fillchar(cost,sizeof(cost),0);
      fillchar(map,sizeof(map),0);
      fillchar(f,sizeof(f),0);
      s:=0;
      t:=n+m+1;
      for j:=1 to m do map[s,j]:=prod[j,i];
      for j:=1 to n do map[m+j,t]:=need[j,i];
      for j:=1 to m do
         for l:=1 to n do
         begin
            map[j,m+l]:=prod[j,i];
            cost[j,m+l]:=fee[i,l,j];
            cost[m+l,j]:=-cost[j,m+l];
         end;
      main:=main+hllp;

   end;

end;
begin
   while not seekeof do
   begin
      read(n,m,k);
      if (n=0) and (m=0) and (k=0) then break;

      fillchar(needk,sizeof(needk),0);
      fillchar(prodk,sizeof(prodk),0);

      for i:=1 to n do
         for j:=1 to k do
         begin
            read(need[i,j]);
            inc(needk[j],need[i,j]);
         end;
      for i:=1 to m do
         for j:=1 to k do
         begin
            read(prod[i,j]);
            inc(prodk[j],prod[i,j]);
         end;
      for i:=1 to k do
         for j:=1 to n do
            for l:=1 to m do
            begin
               read(fee[i,j,l]);
            end;
     writeln(main);



   end;
end.