#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxint 0x7fffffff
#define maxn 52
#define size 2*maxn

int need[maxn][maxn];
int provide[maxn][maxn];
int cost[maxn][maxn][maxn];

int cap[size][size];
int flow[size][size];
int pre[size];
int w[size][size];
int d[size];

int n,m,k;
int S,T;
int min;
int max_flow;
int N;

int Bellman_ford()
{
	int i,j,k;
	memset(pre,0,sizeof(pre));
	for(i=1;i<=N;i++)
		d[i]=maxint;
	d[0]=0;
	for(k=1;k<=N;k++)
		for(i=0;i<=N;i++)
			for(j=0;j<=N;j++)
				if(cap[i][j]-flow[i][j]>0)
					if(d[i]<maxint && d[j]>d[i]+w[i][j]){
						d[j]=d[i]+w[i][j];
						pre[j]=i;
					}
	if(pre[T]!=0)
		return 1;
	else
		return 0;
}
	
int Edmonds_Karp()
{
	int cp,v;
	int ans=0;
	max_flow=0;
	while(Bellman_ford())
	{
		cp=maxint;
		for(v=T;v!=S;v=pre[v])
			if(cp>cap[pre[v]][v]-flow[pre[v]][v])
				cp=cap[pre[v]][v]-flow[pre[v]][v];
		for(v=T;v!=S;v=pre[v])
		{
			flow[pre[v]][v]+=cp;
			flow[v][pre[v]]=-flow[pre[v]][v];
			ans+=cp*w[pre[v]][v];
		}
		max_flow+=cp;
	}
    return ans;
}
int main()
{
	//freopen("f.in","r",stdin);
    int i,j,t,sum;
	for(;;)
	{
		scanf("%d%d%d",&n,&m,&k);
		if(n==0 && m==0 && k==0)
			break;
		for(i=1;i<=n;i++)
			for(j=1;j<=k;j++)
				scanf("%d",&need[i][j]);
		for(i=1;i<=m;i++)
			for(j=1;j<=k;j++)
				scanf("%d",&provide[i][j]);
		for(t=1;t<=k;t++)
			for(i=1;i<=n;i++)
				for(j=1;j<=m;j++)
					scanf("%d",&cost[t][i][j]);
		min=0;
		for(t=1;t<=k;t++)
		{
			memset(flow,0,sizeof(flow));
			memset(cap,0,sizeof(cap));
			memset(w,0,sizeof(w));
			S=0,T=m+n+1,N=m+n+1;
			for(i=1;i<=m;i++)
				cap[S][i]=provide[i][t];
			for(i=1;i<=m;i++)
				for(j=m+1;j<=m+n;j++)
					cap[i][j]=maxint;
			for(i=m+1;i<=m+n;i++)
				cap[i][T]=need[i-m][t];
			for(i=1;i<=m;i++)
				for(j=m+1;j<=m+n;j++)
					w[i][j]=cost[t][j-m][i];

			min+=Edmonds_Karp();
			for(i=1,sum=0;i<=n;i++)
				sum+=need[i][t];
			if(max_flow!=sum)
				break;
		}
		if(t>k)
			printf("%d\n",min);
		else
			printf("-1\n");
	}
	return 0;
}

• Re:为什么俺的最小费用最大流会TLE啊？ (2384) Tiandy 2008-10-11 11:35:17