记录编号	395963	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 运输问题	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2017-04-17 17:48:02	内存使用	8.01 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<vector>
#include<algorithm>
#include<stack>
#include<string>
#define inf 0x7fffff
using namespace std;
int n,m,tmp;
int zx[1002][1002];
int zd[1002][1002];
int zq[1002],cc[1002];
bool pan[1002];
vector<pair<int,int> > xf[1002];
vector<pair<int,int> > df[1002];
queue<int> q;
bool spfax()
{
	memset(cc,0x7f,sizeof(cc));
	memset(zq,0,sizeof(zq));
	pan[0]=1;q.push(0);cc[0]=0;
	while(!q.empty())
	{
		int now=q.front();
		pan[now]=0;q.pop();
		for(int i=0;i<xf[now].size();i++)
		{
			int md=xf[now][i].first,fy=xf[now][i].second;
			if(cc[now]+fy<cc[md]&&zx[now][md]!=0)
			{
				cc[md]=cc[now]+fy;
				zq[md]=now;
				if(!pan[md])
				{
					q.push(md);
					pan[md]=1;
				}
			}
		}
	}
	if(zq[1001]==0)return 0;
	return 1;
}
bool spfad()
{
	memset(cc,0x7f,sizeof(cc));
	memset(zq,0,sizeof(zq));
	pan[0]=1;q.push(0);cc[0]=0;
	while(!q.empty())
	{
		int now=q.front();
		pan[now]=0;q.pop();
		for(int i=0;i<df[now].size();i++)
		{
			int md=df[now][i].first,fy=df[now][i].second;
			if(cc[now]+fy<cc[md]&&zd[now][md]!=0)
			{
				cc[md]=cc[now]+fy;
				zq[md]=now;
				if(!pan[md])
				{
					q.push(md);
					pan[md]=1;
				}
			}
		}
	}
	if(zq[1001]==0)return 0;
	return 1;
}
int dfsx(int now,int flo)
{
	while(zq[now]!=0)
	{
		flo=min(flo,zx[zq[now]][now]);
		if(zq[now]==0)break;
		now=zq[now];
	}
	flo=min(flo,zx[0][now]);
	now=1001;
	while(zq[now]!=0)
	{
		zx[zq[now]][now]-=flo;
		zx[now][zq[now]]+=flo;
		if(zq[now]==0)break;
		now=zq[now];
	}
	zx[0][now]-=flo;zx[now][0]+=flo;
	return flo;
}
int dfsd(int now,int flo)
{
	while(zq[now]!=0)
	{
		flo=min(flo,zd[zq[now]][now]);
		if(zq[now]==0)break;
		now=zq[now];
	}
	flo=min(flo,zd[0][now]);
	now=1001;
	while(zq[now]!=0)
	{
		zd[zq[now]][now]-=flo;
		zd[now][zq[now]]+=flo;
		if(zq[now]==0)break;
		now=zq[now];
	}
	zd[0][now]-=flo;zd[now][0]+=flo;
	return flo;
}
int main()
{
	freopen("tran.in","r",stdin);
	freopen("tran.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&zx[0][i]);
		zd[0][i]=zx[0][i];
		xf[0].push_back(make_pair(i,0));
		xf[i].push_back(make_pair(0,0));
		df[0].push_back(make_pair(i,0));
		df[i].push_back(make_pair(0,0));
	}
	for(int i=m+1;i<=m+n;i++)
	{
		scanf("%d",&zx[i][1001]);
		zd[i][1001]=zx[i][1001];
		xf[1001].push_back(make_pair(i,0));
		xf[i].push_back(make_pair(1001,0));
		df[1001].push_back(make_pair(i,0));
		df[i].push_back(make_pair(1001,0));
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=m+1;j<=m+n;j++)
		{
			int lin;
			scanf("%d",&lin);
			zx[i][j]=inf;
			zd[i][j]=inf;
			xf[i].push_back(make_pair(j,lin));
			xf[j].push_back(make_pair(i,-lin));
			df[i].push_back(make_pair(j,-lin));
			df[j].push_back(make_pair(i,lin));
		}
	}
	while(spfax())
	{
		tmp+=cc[1001]*dfsx(1001,inf);
	}
	printf("%d\n",tmp);
	tmp=0;
	while(spfad())
	{
		tmp+=cc[1001]*dfsd(1001,inf);
	}
	printf("%d",-tmp);
	return 0;
}