内容目录
一开始居然忘添反向边……
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.