对于每个物品进行一次费用流即可,如果只搞一次会超时。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<queue>
#define inf 0x3f
#define maxn 110
#define rep(a,b,i) for(i=a;i<=b;i++)
using namespace std;
struct pi
{
int to;
int cap;
int cost;
int rev;
};
vector<pi>g[maxn];
int dis[maxn];
int pre[maxn],pree[maxn];
int sink,source;
int vis[maxn];
int a[maxn];
int map[55][55];
int map1[55][55];
void add(int a,int b,int cap,int cost)
{
pi pp;
pp.to=b;
pp.cap=cap;
pp.cost=cost;
pp.rev=(int)g[b].size();
g[a].push_back(pp);
pp.to=a;
pp.cap=0;
pp.cost=-cost;
pp.rev=(int)g[a].size()-1;
g[b].push_back(pp);
return ;
}
int spfa(void)
{
int i,p,k;
memset(dis,0x3f ,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
memset(pree,-1,sizeof(pree));
dis[source]=0;
vis[source]=1;
queue<int>q;
pi pp;
q.push(source);
while(!q.empty())
{
p=q.front();
k=(int)g[p].size();
q.pop();
vis[p]=0;
if(p==sink)
continue;
for(i=0;i<k;i++)
{
pp=g[p][i];
if(pp.cap>0&&dis[pp.to]>dis[p]+pp.cost)
{
dis[pp.to]=dis[p]+pp.cost;
pre[pp.to]=p;
pree[pp.to]=i;
if(!vis[pp.to])
{
q.push(pp.to);
vis[pp.to]=1;
}
}
}
}
return pre[sink]!=-1;
}
int min(int a,int b)
{
int p;
p=a;
if(b<a)
p=b;
return p;
}
int minflow(void)
{
int i,f;
int res=0;
while(spfa())
{
f=inf;
for(i=sink;i!=source;i=pre[i])
{
f=min(f,g[pre[i]][pree[i]].cap);
}
res+=f*dis[sink];
for(i=sink;i!=source;i=pre[i])
{
pi &e=g[pre[i]][pree[i]];
e.cap-=f;
g[i][e.rev].cap+=f;
}
}
return res;
}
int main()
{
int i,j,n,m,p,k,f,q;
while(cin>>n>>m>>k){
if(!n&&!m&&!k)
break;
memset(map,0,sizeof(map));
memset(map1,0,sizeof(map1));
for(i=1;i<=n;i++){
for(j=1;j<=k;j++){
scanf("%d",&map[i][j]);
}
}
for(i=1;i<=m;i++){
for(j=1;j<=k;j++){
scanf("%d",&p);
map1[i][j]=p;
}
}
int flag=0;
rep(1,k,i){
p=0;
q=0;
rep(1,n,j){
p+=map[j][i];
}
rep(1,m,j)
q+=map1[j][i];
if(q<p){
flag=1;
break;
}
}
p=0;
for(i=1;i<=k;i++){
rep(0,n+m+1,j){
g[j].clear();
}
rep(1,n,j){
add(m+j,n+m+1,map[j][i],0);
}
rep(1,m,j){
add(0,j,map1[j][i],0);
}
rep(1,n,j){
rep(1,m,f){
scanf("%d",&q);
add(f,m+j,100000000,q);
}
}
if(flag)
continue;
source=0;
sink=n+m+1;
p+=minflow();
}
if(flag){
printf("-1\n");
continue;
}
printf("%d\n",p);
}
return 0;
}