记录编号	387646	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 运输问题	最终得分	100
用户昵称	nonamenotitle	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2017-03-26 23:35:10	内存使用	0.48 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int maxn=200;
const int maxm=200;
const int inf=0x3f3f3f3f;
int n,m;
struct edge
{
	int to,cap,cost,rev;
};
vector<edge> g[maxn];
int a[maxn];
int b[maxn];
int p[maxm][maxn];
int dis[maxn+maxm+2];
int q[maxn+maxm+2];
bool inque[maxn+maxm+2];
int prevv[maxn+maxm+2];
int preve[maxn+maxm+2];
int aj[maxn+maxm+2];
int ans=0;
void addedge(int from,int to,int cap,int cost)
{
	g[from].push_back((edge){to,cap,cost,g[to].size()});
	g[to].push_back((edge){from,0,-cost,g[from].size()-1});
}

bool spfa(int st,int ed)
{
	memset(prevv,0,sizeof(prevv));
	memset(preve,0,sizeof(preve));
	memset(inque,false,sizeof(inque));
	memset(dis,inf,sizeof(dis));
	dis[st]=0;
	memset(q,0,sizeof(q));
	int head=0;
	int tail=0;
	q[head]=st;
	aj[st]=inf;
	inque[st]=true;
	while(head<=tail)
	{
		int top=q[head];
		inque[top]=false;
		head++;
		for(unsigned i=0;i<g[top].size();i++)
		{
			edge &e=g[top][i];
			if(dis[e.to]>dis[top]+e.cost && e.cap>0)
			{
				aj[e.to]=min(e.cap,aj[top]);
				dis[e.to]=dis[top]+e.cost;
				prevv[e.to]=top;
				preve[e.to]=i;
				if(!inque[e.to])
				{
					tail++;
					q[tail]=e.to;
					inque[e.to]=true;
				}
			}
		}
	}
	if(dis[ed]==inf)
	{
		return false;
	}
	ans+=aj[ed]*dis[ed];
	for(int i=ed;i!=st;i=prevv[i])
	{
		edge &e=g[prevv[i]][preve[i]];
		e.cap-=aj[ed];
		g[e.to][e.rev].cap+=aj[ed];
	}
	return true;
}

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",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
	int s=0;
	int t=n+m+1;
	for(int i=1;i<=m;i++)
	{
		addedge(s,i,a[i],0);
	}
	for(int i=1;i<=n;i++)
	{
		addedge(i+m,t,b[i],0);
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int cost;
			scanf("%d",&cost);
			p[i][j]=cost;
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			addedge(i,j+m,inf,p[i][j]);
		}
	}
	
	while(spfa(s,t));
	printf("%d\n",ans);
	//反向后再求
	ans=0;
	for(int i=0;i<maxn;i++)
	{
		g[i].clear();
	}
	for(int i=1;i<=m;i++)
	{
		addedge(s,i,a[i],0);
	}
	for(int i=1;i<=n;i++)
	{
		addedge(i+m,t,b[i],0);
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			addedge(i,j+m,inf,-p[i][j]);
		}
	}
	while(spfa(s,t));
	printf("%d\n",-ans);
	return 0;
}