#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 305
#define NN 100000
#define M NN
#define inf 0x3fffffff
using namespace std;
struct Syndra
{
	int u,v,w,len,next;
}e[M];
int head[N],cnt;//for Syndra
int pre[N],mc[N],s,t;//for costflow
int need[N][N],offer[N][N],carriage[N][N][N];//for build
int spfa(int s,int t)
{
	int i,j,k;
	int u,v;
	int dist[N],visit[N];
	queue<int>q;
	memset(dist,0x3f,sizeof(dist));
	memset(visit,0,sizeof(visit));
	memset(pre,-1,sizeof(pre));
	memset(mc,0x3f,sizeof(mc));
	dist[s]=0;
	visit[s]=1;
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		visit[u]=0;
		for(i=head[u];i;i=e[i].next)
		{
			v=e[i].v;
			if(e[i].len&&dist[v]>dist[u]+e[i].w)
			{
				dist[v]=dist[u]+e[i].w;
				pre[v]=i;
				mc[v]=min(mc[u],e[i].len);
				if(!visit[v])
				{
					q.push(v);
					visit[v]=1;
				}
			}
		}
	}
	if(dist[t]<0x3f3f3f3f)return dist[t];
	else return -1;
}
void handle(int flow)
{
	int i;
	for(i=t;pre[i]+1;i=e[pre[i]].u)
	{
		e[pre[i]].len-=flow;
		e[pre[i]^1].len+=flow;
	}
}
void add(int u,int v,int w,int len)
{
	++cnt;
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].len=len;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void build(int n,int m,int p)
{
	int i,j,k;
	memset(head,0,sizeof(head));
	cnt=1;s=0;t=n+m+1;
	for(i=1;i<=m;i++)
	{
		add(s,i,0,offer[p][i]);
		add(i,s,0,0);
	}
	for(i=1;i<=n;i++)
	{
		add(i+m,t,0,need[p][i]);
		add(t,i+m,0,0);
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			add(i,j+m,carriage[p][i][j],inf);
			add(j+m,i,-carriage[p][i][j],0);
		}
	}
}

int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k;
	int ans,sum;
	int n,m,p;
	int sum_of_offer[N],sum_of_need[N],flag;
	while(scanf("%d%d%d",&n,&m,&p),n+m+p)
	{
		ans=0;flag=1;
		memset(sum_of_need,0,sizeof(sum_of_need));
		memset(sum_of_offer,0,sizeof(sum_of_offer));
		for(i=1;i<=n;i++)for(j=1;j<=p;j++)scanf("%d",&need[j][i]),sum_of_need[j]+=need[j][i];
		for(i=1;i<=m;i++)for(j=1;j<=p;j++)scanf("%d",&offer[j][i]),sum_of_offer[j]+=offer[j][i];
		for(i=1;i<=p;i++)for(j=1;j<=n;j++)for(k=1;k<=m;k++)scanf("%d",&carriage[i][k][j]);
		for(i=1;i<=p;i++)
		{
			if(sum_of_offer[i]<sum_of_need[i])
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			printf("-1\n");
			continue;
		}
		for(i=1;i<=p;i++)
		{
			build(n,m,i);
			sum=0;
			while(k=spfa(s,t),k+1)
			{
				sum+=mc[t]*k;
				handle(mc[t]);
			}
			ans+=sum;
		}
		printf("%d\n",ans);
	}
	return 0;
}

• 我也贴一个 (2137) qq2308091457 2016-08-13 09:54:31