记录编号	143460	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]happiness(吴确)	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.614 s
提交时间	2014-12-14 21:35:24	内存使用	1.44 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int SIZEN=10010,SIZEn=110;
const LL INF=1e16;
class Edge{
public:
	int from,to;
	LL cap,flow;
};
vector<Edge> edges;
int N,S,T;
vector<int> c[SIZEN];
void addedge(int from,int to,int cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
int depth[SIZEN],cur[SIZEN];
bool BFS(void){
	static bool vis[SIZEN];
	static queue<int> Q;
	memset(vis,0,sizeof(vis));
	while(!Q.empty()) Q.pop();
	depth[S]=0;vis[S]=true;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			Edge &e=edges[c[x][i]];
			if(e.cap>e.flow&&!vis[e.to]){
				depth[e.to]=depth[x]+1;
				vis[e.to]=true;
				Q.push(e.to);
			}
		}
	}
	return vis[T];
}
LL DFS(int x,LL a){
	if(x==T||!a) return a;
	LL ans=0;
	for(int &i=cur[x];i<c[x].size();i++){
		Edge &e=edges[c[x][i]];
		if(depth[x]+1==depth[e.to]){
			LL cf=DFS(e.to,min(e.cap-e.flow,a));
			if(cf){
				ans+=cf;a-=cf;
				e.flow+=cf;edges[c[x][i]^1].flow-=cf;
			}
			if(!a) break;
		}
	}
	if(!ans) depth[x]=-1;
	return ans;
}
LL Dinic(void){
	LL ans=0;
	while(BFS()){
		memset(cur,0,sizeof(cur));
		ans+=DFS(S,INF);
	}
	return ans;
}
int n,m;
int hash(int i,int j){return i*m+j;}
//上下左右=0123
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
LL allsum=0;
void read_matrix(LL s[SIZEn][SIZEn],int n,int m){
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%lld",&s[i][j]),allsum+=s[i][j];//注意allsum累加
}
//文=we,理=li
LL we[SIZEn][SIZEn],li[SIZEn][SIZEn];
LL cwe[4][SIZEn][SIZEn],cli[4][SIZEn][SIZEn];//和某个方向的同学同为文/理
void makegraph(void){
	scanf("%d%d",&n,&m);
	N=n*m+1,S=N-1,T=N;
	read_matrix(we,n,m);
	read_matrix(li,n,m);
	read_matrix(cwe[1],n-1,m);
	read_matrix(cli[1],n-1,m);
	read_matrix(cwe[3],n,m-1);
	read_matrix(cli[3],n,m-1);
	for(int i=0;i<n-1;i++)
		for(int j=0;j<m;j++) cwe[0][i+1][j]=cwe[1][i][j],cli[0][i+1][j]=cli[1][i][j];
	for(int i=0;i<n;i++)
		for(int j=0;j<m-1;j++) cwe[2][i][j+1]=cwe[3][i][j],cli[2][i][j+1]=cli[3][i][j];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if((i+j)&1){
				addedge(S,hash(i,j),we[i][j]+cwe[0][i][j]+cwe[1][i][j]+cwe[2][i][j]+cwe[3][i][j]);
				addedge(hash(i,j),T,li[i][j]+cli[0][i][j]+cli[1][i][j]+cli[2][i][j]+cli[3][i][j]);
				for(int d=0;d<4;d++){
					int i1=i+dx[d],j1=j+dy[d];
					if(0<=i1&&i1<n&&0<=j1&&j1<m){
						addedge(hash(i,j),hash(i1,j1),cwe[d][i][j]);
					}
				}
			}
			else{
				addedge(S,hash(i,j),we[i][j]);
				addedge(hash(i,j),T,li[i][j]);
				for(int d=0;d<4;d++){
					int i1=i+dx[d],j1=j+dy[d];
					if(0<=i1&&i1<n&&0<=j1&&j1<m){
						addedge(hash(i,j),hash(i1,j1),cli[d][i][j]);
					}
				}
			}
		}
	}
}
int main(){
	freopen("nt2011_happiness.in","r",stdin);
	freopen("nt2011_happiness.out","w",stdout);
	makegraph();
	printf("%lld\n",allsum-Dinic());
	return 0;
}