记录编号	431555	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]happiness(吴确)	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.467 s
提交时间	2017-08-01 06:32:18	内存使用	22.24 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 100000007
#define int long long
int read() {
	int s=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') {
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
int n,m,sum;
int wen_sin[101][101],li_sin[101][101],wen_xia[101][101],li_xia[101][101],wen_you[101][101],li_you[101][101];
int dis[102][102],num[101][101],zong,tot,S,T,r[10005];
int sum_li[10002],sum_wen[10002];
struct oo {
	int to,vv,next;
} c[1000005];
void add(int x,int y,int z) {
	c[tot].to=y;
	c[tot].vv=z;
	c[tot].next=r[x];
	r[x]=tot++;
}
void init() {
	memset(r,-1,sizeof(r));
	n=read();
	m=read();
	T=n*m+1;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			num[i][j]=++zong;
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			wen_sin[i][j]=read()*2;
			sum+=wen_sin[i][j];
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			li_sin[i][j]=read()*2;
			sum+=li_sin[i][j];
		}
	}
	for(int i=1; i<n; i++) {
		for(int j=1; j<=n; j++) {
			wen_xia[i][j]=read()*2;
			sum_wen[num[i][j]]+=wen_xia[i][j];
			sum_wen[num[i+1][j]]+=wen_xia[i][j];
			sum+=wen_xia[i][j];
		}
	}
	for(int i=1; i<n; i++) {
		for(int j=1; j<=m; j++) {
			li_xia[i][j]=read()*2;
			sum_li[num[i][j]]+=li_xia[i][j];
			sum_li[num[i+1][j]]+=li_xia[i][j];
			sum+=li_xia[i][j];
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<m; j++) {
			wen_you[i][j]=read()*2;
			sum_wen[num[i][j]]+=wen_you[i][j];
			sum_wen[num[i][j+1]]+=wen_you[i][j];
			sum+=wen_you[i][j];
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<m; j++) {
			li_you[i][j]=read()*2;
			sum_li[num[i][j]]+=li_you[i][j];
			sum_li[num[i][j+1]]+=li_you[i][j];
			sum+=li_you[i][j];
		}
	}
}
// S li T wen
void build() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			int x=li_sin[i][j]+sum_li[num[i][j]]/2;
			add(S,num[i][j],x);
			add(num[i][j],S,0);
			int y=wen_sin[i][j]+sum_wen[num[i][j]]/2;
			add(num[i][j],T,y);
			add(T,num[i][j],0);
			if(i<n) {
				add(num[i][j],num[i+1][j],(li_xia[i][j]+wen_xia[i][j])/2);
				add(num[i+1][j],num[i][j],0);
				add(num[i+1][j],num[i][j],(li_xia[i][j]+wen_xia[i][j])/2);
				add(num[i][j],num[i+1][j],0);
			}
			if(j<m) {
				add(num[i][j],num[i][j+1],(li_you[i][j]+wen_you[i][j])/2);
				add(num[i][j+1],num[i][j],0);
				add(num[i][j+1],num[i][j],(li_you[i][j]+wen_you[i][j])/2);
				add(num[i][j],num[i][j+1],0);
			}
		}
	}
}
int queue[1000005],head,tail,deep[10005];
bool vis[10005];
bool bfs(int s,int t) {
	memset(deep,0,sizeof(deep));
	memset(vis,0,sizeof(vis));
	head=tail=0;
	deep[s]=1;
	vis[s]=1;
	queue[++tail]=s;
	while(head<tail) {
		int opt=queue[++head];
		vis[opt]=0;
		for(int i=r[opt]; ~i; i=c[i].next) {
			if(c[i].vv&&!deep[c[i].to]) {
				deep[c[i].to]=deep[opt]+1;
				if(!vis[c[i].to]){
					queue[++tail]=c[i].to;
					vis[c[i].to]=1;
				}
				if(c[i].to==t) {
					return 1;
				}
			}
		}
	}
	return 0;
}
int dfs(int opt,int fw) {
	if(opt==T) {
		return fw;
	}
	int tmp=fw,k;
	for(int i=r[opt]; ~i; i=c[i].next) {
		if(tmp&&c[i].vv&&deep[c[i].to]==deep[opt]+1) {
			k=dfs(c[i].to,min(c[i].vv,tmp));
			if(!k) {
				deep[c[i].to]=0;
				continue;
			}
			c[i].vv-=k;
			c[i^1].vv+=k;
			tmp-=k;
		}
	}
	return fw-tmp;
}
int dinic(int s,int t) {
	int ans=0;
	while(bfs(s,t)) {
		ans+=dfs(s,inf);
	}
	return ans;
}
int Main(){
	freopen("nt2011_happiness.in","r",stdin);
	freopen("nt2011_happiness.out","w",stdout);
	init();
	build();
	int ans=dinic(S,T);
	printf("%d\n",(sum-ans)>>1);
	return 0;
}
int hehe=Main();
signed main() {
	;
}