记录编号	431395	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]happiness(吴确)	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.316 s
提交时间	2017-07-31 17:48:43	内存使用	11.22 MiB

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int M=100+10;
const int N=1000000+10;
const int inf=0x7fffffff;
int n,m,S,T,num=1,sum,js,ans;
int dep[M*M],head[N],sum_chi[M*M],sum_math[M*M];
int chi[M][M],math[M][M],chi_ud[M][M],math_ud[M][M],chi_lr[M][M],math_lr[M][M],numb[M][M];
struct DATE{int to,w,last;}date[N];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void add(int x,int y,int z){
	date[++num]=(DATE){y,z,head[x]};
	head[x]=num;
}
inline void forr(int fir,int se,int a[110][110]){
	for(int i=1;i<=fir;i++){
		for(int j=1;j<=se;j++){
			a[i][j]=read()*2;
			sum+=a[i][j];
		}
	}
}
inline void ffor(int fir,int se,int a[110][110],int b[12100]){
	for(int i=1;i<=fir;i++){
		for(int j=1;j<=se;j++){
			a[i][j]=read()*2;
			b[numb[i][j]]+=a[i][j];
			b[numb[i+1][j]]+=a[i][j];
			sum+=a[i][j];
		}
	}
}
inline void fforr(int fir,int se,int a[110][110],int b[12100]){
	for(int i=1;i<=fir;i++){
		for(int j=1;j<=se;j++){
			a[i][j]=read()*2;
			b[numb[i][j]]+=a[i][j];
			b[numb[i][j+1]]+=a[i][j];
			sum+=a[i][j];
		}
	}
}
inline void init(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			numb[i][j]=++js;
	forr(n,m,chi);forr(n,m,math);
	ffor(n-1,m,chi_ud,sum_chi);ffor(n-1,m,math_ud,sum_math);
	fforr(n,m-1,chi_lr,sum_chi);fforr(n,m-1,math_lr,sum_math);
}
inline void makemap(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=chi[i][j]+(sum_chi[numb[i][j]]>>1);
			int y=math[i][j]+(sum_math[numb[i][j]]>>1);
			add(S,numb[i][j],x),add(numb[i][j],S,0);
			add(numb[i][j],T,y),add(T,numb[i][j],0);
			if(i<n){
				int he=chi_ud[i][j]+math_ud[i][j]>>1;
				add(numb[i][j],numb[i+1][j],he);
				add(numb[i+1][j],numb[i][j],0);
				add(numb[i][j],numb[i+1][j],0);
				add(numb[i+1][j],numb[i][j],he);
			}
			if(j<m){
				int he=chi_lr[i][j]+math_lr[i][j]>>1;
				add(numb[i][j],numb[i][j+1],he);
				add(numb[i][j+1],numb[i][j],0);
				add(numb[i][j],numb[i][j+1],0);
				add(numb[i][j+1],numb[i][j],he);
			}
		}	
	}
}
bool bfs(){
	memset(dep,0,sizeof(dep));
	queue<int> pq;
	pq.push(S);
	dep[S]=1;
	while(!pq.empty()){
		int now=pq.front();pq.pop(); 
		for(int i=head[now];i;i=date[i].last){
			int to=date[i].to;
			if(date[i].w&&!dep[to]){
				dep[to]=dep[now]+1;
				pq.push(to);
				if(to==T) return true;
			}
		}
	}
	return false;
}
int dfs(int now,int fw){
	if(now==T) return fw;
	int tmp=fw;
	for(int i=head[now];i;i=date[i].last){
		int to=date[i].to;
		if(date[i].w&&tmp&&dep[to]==dep[now]+1){
			int k=dfs(to,min(date[i].w,tmp));
			if(!k){dep[to]=0;continue;}
			date[i].w-=k;
			date[i^1].w+=k;
			tmp-=k;
		}
	}
	return fw-tmp;
}
inline void dinic(){
	while(bfs()) ans+=dfs(S,inf);
	ans=sum-ans>>1;
	printf("%d",ans);
}
int DK(){
	freopen("nt2011_happiness.in","r",stdin);
	freopen("nt2011_happiness.out","w",stdout);
	n=read();m=read();T=n*m+1;
	init();
	makemap();
	dinic();
	return 0;
}
int dk=DK();
int main(){
	;
}