记录编号	366171	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]happiness(吴确)	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.156 s
提交时间	2017-01-22 23:44:02	内存使用	21.38 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=5e5+10,V=110;
struct edge{int f,t,g,o;}w[N];
int n,m,s,t,ans,cnt,a[V][V],p[V][V];
int head[N],tail[N],next[N];
void add(int f,int t,int g){
	static int cnt=0;
	++cnt;w[cnt]=(edge){f,t,g,cnt+1};
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	++cnt;w[cnt]=(edge){t,f,0,cnt-1};
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
struct st{int x,i,df;}z[N];
int l[N],top;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	int df=F;ans-=df;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[w[z[i].i].o].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=s;i<=cnt;i++) l[i]=0;
	l[s]=1;Q.push(s);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[t]) return 0;
	z[top=1]=(st){s,head[s],(int)1e9};
	while (top){
		if (V==t){change();top--;E=next[E];}else
		if (!E){l[V]=0;top--;E=next[E];}else
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=(st){w[E].t,head[w[E].t],min(w[E].g,F)},top++;
		else E=next[E]; 
	}
	return 1;
}
int main()
{
	freopen("nt2011_happiness.in","r",stdin);
	freopen("nt2011_happiness.out","w",stdout); 
	scanf("%d%d",&n,&m);
	s=0;t=cnt=1;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++){
		scanf("%d",&a[i][j]);
		p[i][j]=++cnt;
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++){
		int x;scanf("%d",&x);
		a[i][j]-=x;ans+=x;
		if (a[i][j]>0) add(s,p[i][j],a[i][j]),ans+=a[i][j];
			else add(p[i][j],t,-a[i][j]);
	}
	for (int i=1;i<n;i++)
	for (int j=1;j<=m;j++){
		int x;scanf("%d",&x);
		ans+=x;++cnt;
		add(s,cnt,x);
		add(cnt,p[i][j],1e9);
		add(cnt,p[i+1][j],1e9);
	}
	for (int i=1;i<n;i++)
	for (int j=1;j<=m;j++){
		int x;scanf("%d",&x);
		ans+=x;++cnt;
		add(cnt,t,x);
		add(p[i][j],cnt,1e9);
		add(p[i+1][j],cnt,1e9);
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<m;j++){
		int x;scanf("%d",&x);
		ans+=x;++cnt;
		add(s,cnt,x);
		add(cnt,p[i][j],1e9);
		add(cnt,p[i][j+1],1e9);
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<m;j++){
		int x;scanf("%d",&x);
		ans+=x;++cnt;
		add(cnt,t,x);
		add(p[i][j],cnt,1e9);
		add(p[i][j+1],cnt,1e9);
	}
	while (dinic());
	printf("%d\n",ans);
	return 0;
}