记录编号	154709	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]happiness(吴确)	最终得分	100
用户昵称	真呆菌	是否通过	通过
代码语言	C++	运行时间	0.700 s
提交时间	2015-03-24 09:25:01	内存使用	5.35 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF = ~0u>>1;
const int N =  20100;
const int M = 400100;
int S,T,n,m,cnt=1;
int to[M],next[M],res[M],head[N],dis[N],g[N];
int f[110][110],ax[110][110],ay[110][110],a[110][110],b[110][110];
long long Ans,Count;
queue<int> q;

int Min(int x,int y){if(x>y) return y;return x;}

void Add(int u,int v,int w){
	to[++cnt]=v;next[cnt]=head[u];head[u]=cnt;res[cnt]=w;
	to[++cnt]=u;next[cnt]=head[v];head[v]=cnt;res[cnt]=0;
}

bool Bfs(){
	memset(dis,0,sizeof(dis));
	dis[S]=1;q.push(S);int k,p;
	while(!q.empty()){
		k=q.front();q.pop();
		for(int i=head[k];i;i=next[i]){
			p=to[i];
			if(dis[p]!=0||res[i]<=0) continue;
			dis[p]=dis[k]+1;
			q.push(p);
		}
	}
	return dis[T];
}

int Dfs(int x,int a){
	if(x==T||a==0) return a;
	int flow=0,f;
	for(int  & i=g[x];i;i=next[i]){
		if( res[i]<=0 || dis[to[i]]!=dis[x]+1) continue;
		f=Dfs(to[i],Min(a,res[i]));
		if(f<=0) continue;	
		flow+=f;a-=f;
		res[i]-=f;res[i^1]+=f;
		if(a==0) break;
	}
	return flow;
}

int main(){
	#define Read
	#ifdef Read
		freopen("nt2011_happiness.in","r",stdin);
		freopen("nt2011_happiness.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);S=0,T=n*m+1;
	for(int ct=0,i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ct++;
			f[i][j]=ct;
		}
	}
	int x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&x);
			Ans+=x;a[i][j]=(x<<1);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&x);
			Ans+=x;b[i][j]=(x<<1);
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&x);
			Ans+=x;
			ax[i][j]+=x;
			a[i][j]+=x;a[i+1][j]+=x;
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&x);
			Ans+=x;
			ax[i][j]+=x;
			b[i][j]+=x;b[i+1][j]+=x;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			scanf("%d",&x);
			Ans+=x;
			ay[i][j]+=x;
			a[i][j]+=x;a[i][j+1]+=x;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			scanf("%d",&x);
			Ans+=x;
			ay[i][j]+=x;
			b[i][j]+=x;b[i][j+1]+=x;
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=m;j++){
			Add(f[i][j],f[i+1][j],ax[i][j]);
			Add(f[i+1][j],f[i][j],ax[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			Add(f[i][j],f[i][j+1],ay[i][j]);
			Add(f[i][j+1],f[i][j],ay[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			Add(S,f[i][j],a[i][j]);
			Add(f[i][j],T,b[i][j]);
		}
	}
	while(Bfs()){ 
		for(int i=S;i<=T;i++) g[i]=head[i];
		Count+=Dfs(S,INF);
	}
	Count/=2;
 	printf("%lld\n",Ans-Count);
	return 0;	
}