1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstring> 7 using namespace std; 8 9 #define inf 0x3f3f3f3f 10 11 int supply[55],demand[55];//某种商品的提供量和需求量 12 int dis[110],pre[110],s,t;//s为超级源点，t为超级汇点 13 int order[55][55];//第i个商店对第j种物品的需求 14 int store[55][55];//第i个供应站对第j个物品的存储量 15 int flow[110][110],cap[110][110];//边的流量,容量 16 int cost[55][55][55];//cost[k][j][i]第k种商品从第j个供应站运到第i个商店的花费 17 int kcost[110][110];//每件商品在某一条边的花费。从供应站到商店方向 18 int vis[110]; 19 int n,m,k; 20 21 int spfa() 22 { 23 queue<int>q; 24 memset(vis,0,sizeof(vis)); 25 memset(pre,-1,sizeof(pre)); 26 q.push(s); 27 fill(&dis[1],&dis[n+m+2],inf);//dis[1----n+m+1]==inf 28 dis[s]=0; 29 vis[s]=1; 30 while(!q.empty()) 31 { 32 int cur=q.front();q.pop(); 33 vis[cur]=0; 34 for(int i=0;i<=n+m+1;i++) 35 { 36 if(cap[cur][i] >flow[cur][i] && dis[i] > dis[cur] + kcost[cur][i]) 37 { 38 dis[i]=dis[cur]+kcost[cur][i]; 39 pre[i]=cur; 40 if(!vis[i]) 41 { 42 vis[i]=1; 43 q.push(i); 44 } 45 } 46 } 47 } 48 return pre[t]!=-1;//pre[t]==-1表示无增广路 49 } 50 51 void costflow() 52 { 53 int minf=inf; 54 while(spfa()) 55 { 56 for(int u=t;pre[u] != -1;u=pre[u]) 57 { 58 minf=min(minf,cap[pre[u]][u]-flow[pre[u]][u]); 59 } 60 for(int u=t;pre[u] !=-1 ;u=pre[u])//沿着最小费用路进行增广 61 { 62 flow[pre[u]][u]+=minf; 63 flow[u][pre[u]]-=minf; 64 } 65 } 66 } 67 68 int main() 69 { 70 while(scanf("%d%d%d",&n,&m,&k)) 71 { 72 if(!n && !m && !k) break; 73 int flag=1;//判断是否无解 74 memset(supply,0,sizeof(supply)); 75 memset(demand,0,sizeof(demand)); 76 for(int i=1;i<=n;i++) 77 { 78 for(int j=1;j<=k;j++) 79 { 80 scanf("%d",&order[i][j]); 81 demand[j]+=order[i][j]; 82 } 83 } 84 for(int i=1;i<=m;i++) 85 { 86 for(int j=1;j<=k;j++) 87 { 88 scanf("%d",&store[i][j]); 89 supply[j]+=store[i][j]; 90 } 91 } 92 for(int p=1;p<=k;p++) 93 { 94 for(int i=1;i<=n;i++) 95 { 96 for(int j=1;j<=m;j++) 97 { 98 scanf("%d",&cost[p][j][i]); 99 } 100 } 101 } 102 for(int i=1;i<=k;i++) 103 { 104 if(demand[i]>supply[i]) 105 { 106 flag=0; 107 break; 108 } 109 } 110 int flowcost=-1; 111 if(flag) 112 { 113 s=0; 114 t=n+m+1; 115 //按照商品数构图k次 116 //cap,kcost，下标1----m为供应站,m+1--m+n为商店 117 flowcost=0; 118 for(int p=1;p<=k;p++) 119 { 120 memset(cap,0,sizeof(cap)); 121 memset(kcost,0,sizeof(kcost)); 122 memset(flow,0,sizeof(flow)); 123 for(int i=1;i<=m;i++)//源点到供应站建边 124 cap[s][i]=store[i][p]; 125 for(int i=1;i<=n;i++) 126 cap[i+m][t]=order[i][p]; 127 for(int i=1;i<=m;i++) 128 { 129 for(int j=1;j<=n;j++) 130 { 131 cap[i][j+m]=store[i][p]; 132 kcost[i][j+m]=cost[p][i][j]; 133 kcost[j+m][i]=-cost[p][i][j];//负费用,表示回流费用增加 134 } 135 } 136 costflow(); 137 for(int i=1;i<=m;i++) 138 { 139 for(int j=1;j<=n;j++) 140 flowcost+=kcost[i][j+m]*flow[i][j+m];//单价乘流量 141 } 142 } 143 } 144 printf("%d\n",flowcost); 145 } 146 return 0; 147 }