记录编号	157922	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 运输问题	最终得分	100
用户昵称	vampire	是否通过	通过
代码语言	C++	运行时间	0.184 s
提交时间	2015-04-11 16:32:13	内存使用	15.59 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 210000000
using namespace std;
int n,m,a[1000],b[1000],co[1000][1000],map[1000][1000][2]={0},dis[1000],l[1000000],pre[1000];
bool f[1000];
int SPFA(int x,int y,int kind)
{
	memset(pre,0,sizeof(pre));
	memset(f,1,sizeof(f));
	if(kind==1) memset(dis,127/3,sizeof(dis));
	else memset(dis,128,sizeof(dis));
	int h=1,t=1,i,u;
	l[h]=x;dis[x]=0;pre[x]=x;
	while(h<=t){
		u=l[h];f[u]=true;
		for(i=1;i<=y;++i){
			if(map[u][i][0]>0)
			  if((kind==1&&dis[i]>dis[u]+map[u][i][1])||(kind==2&&dis[i]<dis[u]+map[u][i][1])){
				dis[i]=dis[u]+map[u][i][1];
				pre[i]=u;
				if(f[i]){
					f[i]=false;
					t+=1;
					l[t]=i;
				}
			}
		}
		h+=1;
	}
	if(kind==1) return dis[y]>10000000?0:dis[y];
	else return dis[y]<0?0:dis[y];
}
int ISAP(int x,int y)
{
    int i,minn=inf;
	for(i=y;i!=x;i=pre[i]){
		minn=min(minn,map[pre[i]][i][0]);
	}
	for(i=y;i!=x;i=pre[i]){
		map[pre[i]][i][0]-=minn;
		map[i][pre[i]][0]+=minn;
	}
	return minn;
}
int main()
{
	freopen("tran.in","r",stdin);
	freopen("tran.out","w",stdout);
    int i,j;
	scanf("%d%d",&m,&n);
	for(i=1;i<=m;++i) scanf("%d",&a[i]);
	for(i=1;i<=n;++i) scanf("%d",&b[i]);
	for(i=1;i<=m;++i)
	  for(j=1;j<=n;++j)
	    scanf("%d",&co[i][j]);
	for(i=1;i<=m;++i){
		map[1][i+1][0]=a[i];
		map[1][i+1][1]=0;
	}
	for(i=1;i<=n;++i){
		map[m+1+i][n+m+2][0]=b[i];
		map[m+1+i][n+m+2][1]=0;
	}
	for(i=1;i<=m;++i){
		for(j=1;j<=n;++j){
			map[i+1][m+1+j][0]=inf;
			map[i+1][m+1+j][1]=co[i][j];
			map[m+1+j][i+1][1]=-co[i][j];
		}
	}
	int minn=1,ans=0;
	while(minn){
		minn=SPFA(1,n+m+2,1);
		if(minn) ans+=minn*ISAP(1,n+m+2);
	}
	printf("%d\n",ans);
	memset(map,0,sizeof(map));
	for(i=1;i<=m;++i){
		map[1][i+1][0]=a[i];
		map[1][i+1][1]=0;
	}
	for(i=1;i<=n;++i){
		map[m+1+i][n+m+2][0]=b[i];
		map[m+1+i][n+m+2][1]=0;
	}
	for(i=1;i<=m;++i){
		for(j=1;j<=n;++j){
			map[i+1][m+1+j][0]=inf;
			map[i+1][m+1+j][1]=co[i][j];
			map[m+1+j][i+1][1]=-co[i][j];
		}
	}
	minn=1,ans=0;
	while(minn){
		minn=SPFA(1,m+n+2,2);
		if(minn) ans+=minn*ISAP(1,m+n+2);
	}
	printf("%d\n",ans);
}