记录编号	285193	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 运输问题	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-07-21 11:01:05	内存使用	0.40 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=510;
const int maxm=8010;
const int INF=100000000;
int cnt=1,fir[maxn],nxt[maxm];
int to[maxm],cap[maxm],val[maxm];
void addedge(int a,int b,int c,int v){
	nxt[++cnt]=fir[a];to[cnt]=b;
	cap[cnt]=c;val[cnt]=v;fir[a]=cnt;
}

queue<int>q;
int path[maxn];
int dis[maxn],vis[maxn];
int Spfa(int S,int T){
	for(int i=S+1;i<=T;i++)
		dis[i]=INF;
	q.push(S);vis[S]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();vis[x]=0;
		for(int i=fir[x];i;i=nxt[i])
			if(cap[i]&&dis[to[i]]>dis[x]+val[i]){
				dis[to[i]]=dis[x]+val[i];
				if(!vis[to[i]])q.push(to[i]);
				vis[to[i]]=1;path[to[i]]=i;
			}
	}
	return dis[T]==INF?0:dis[T];
}

int Aug(int S,int T){
	int f=INF,p=T;
	while(p!=S){
		f=min(f,cap[path[p]]);
		p=to[path[p]^1];
	}
	p=T;
	while(p!=S){
		cap[path[p]]-=f;
		cap[path[p]^1]+=f;
		p=to[path[p]^1];
	}
	return f;
}

int MCMF(int S,int T){
	int ret=0,d;
	while(d=Spfa(S,T))
		ret+=Aug(S,T)*d;
	return ret;
}

int S,T;
int n,m;
int main(){
	freopen("tran.in","r",stdin);
	freopen("tran.out","w",stdout);
	scanf("%d%d",&m,&n);S=0;T=n+m+1;
	for(int i=1,x;i<=m;i++){
		scanf("%d",&x);
		addedge(S,i,x,0);
		addedge(i,S,0,0);
	}
	
	for(int i=m+1,x;i<=m+n;i++){
		scanf("%d",&x);
		addedge(i,T,x,0);
		addedge(T,i,0,0);
	}
	
	for(int i=1;i<=m;i++)
		for(int j=m+1,x;j<=n+m;j++){
			scanf("%d",&x);
			addedge(i,j,INF,x);
			addedge(j,i,0,-x);
		}
	printf("%d\n",MCMF(S,T));
	for(int i=2;i<=cnt;i+=2){
		val[i]*=-1;
		val[i^1]*=-1;
		cap[i]+=cap[i^1];
		cap[i^1]=0;
	}
	printf("%d\n",-MCMF(S,T));	
	return 0;
}