【题意】
有n个商店m个供应商k种商品
给各商店的各种商品的需求量和各供应商的供应量以及供应商和商店之间的运输费用,求满足需求的最小费用
【输入】
多组数据
每组数据第一行n,m,k(均小于50)
接下来n行每行k个数,表示需求量(0到3)
接下来m行每行k个数,表示供应量(0到3)
接下来k个n*m矩阵表示商店和供应商之间的运输费用
输入由第一行三个0结束
【输出】
每组数据输出一个数,表示最小费用
最小费用最大流,对于每种商品来一次。
program poj2516; var sqn,sqm,cost,flow:array [0..101,0..101] of longint; dis,last:array [0..101] of longint; dl:array [0..10001] of longint; ans,i,j,k,n,m,tot,a,b:longint; procedure maxflow; var i,j,k,answer:longint; begin answer:=0; repeat fillchar(dis,sizeof(dis),63); tot:=1; dl[1]:=0; dis[0]:=0; i:=1; while i<=tot do begin for j:=1 to n+m+1 do if flow[dl[i],j]>0 then if dis[dl[i]]+cost[dl[i],j]<dis[j] then begin dis[j]:=dis[dl[i]]+cost[dl[i],j]; inc(tot); dl[tot]:=j; last[j]:=dl[i]; end; inc(i); end; if dis[n+m+1]>1000000 then break; i:=n+m+1; k:=maxlongint; while i<>0 do begin if flow[last[i],i]<k then k:=flow[last[i],i]; i:=last[i]; end; answer:=answer+k*dis[n+m+1]; i:=n+m+1; while i<>0 do begin flow[last[i],i]:=flow[last[i],i]-k; flow[i,last[i]]:=flow[i,last[i]]+k; i:=last[i]; end; until false; ans:=ans+answer; end; begin repeat read(n,m,k); if n=0 then break; for i:=1 to n do for j:=1 to k do read(sqn[i,j]); for i:=1 to m do for j:=1 to k do read(sqm[i,j]); ans:=0; for i:=1 to k do begin fillchar(flow,sizeof(flow),0); fillchar(cost,sizeof(cost),0); a:=0; for j:=1 to n do begin a:=a+sqn[j,i]; flow[j,n+m+1]:=sqn[j,i]; end; b:=0; for j:=1 to m do begin b:=b+sqm[j,i]; flow[0,n+j]:=sqm[j,i]; end; if a>b then ans:=-1; for a:=1 to n do for b:=1 to m do begin read(cost[n+b,a]); cost[a,n+b]:=-cost[n+b,a]; flow[n+b,a]:=maxlongint div 10; end; if ans<>-1 then maxflow; end; writeln(ans); until false; end.