记录编号	430485	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]happiness(吴确)	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	0.499 s
提交时间	2017-07-29 20:35:55	内存使用	43.15 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int N=120,inf=0x7fffffff;
const int S=10011,T=10012;
int n,m,num[N][N],e=1,adj[N*N],sum,ans;
int self[N][N][3],row[N][N][3],line[N][N][3];
struct node{int zhong,next,flow;}s[N*N<<8];
inline void add(int qi,int zhong,int flow)
	{s[++e].zhong=zhong,s[e].flow=flow;s[e].next=adj[qi];adj[qi]=e;}
queue<int>q;
int d[N*N];
inline bool bfs()
{
	memset(d,-1,sizeof(d));
	d[S]=1,q.push(S);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=adj[x];i;i=s[i].next)
		{
			int u=s[i].zhong;
			if(d[u]==-1&&s[i].flow)
				d[u]=d[x]+1,q.push(u);
		}
	}
	return d[T]!=-1;
}
int dfs(int rt,int maxf)
{
	if(rt==T||maxf==0)return maxf;
	int ret=0;
	for(int i=adj[rt];i;i=s[i].next)
		if(s[i].flow)
		{
			int u=s[i].zhong;
			if(d[u]!=d[rt]+1)continue;
			int f=dfs(u,min(s[i].flow,maxf));
			maxf-=f,ret+=f;
			s[i].flow-=f,s[i^1].flow+=f;
			if(!maxf)break;
		}
	if(!ret)d[rt]=-1;
	return ret;
}
int main()
{
	freopen("nt2011_happiness.in","r",stdin);
	freopen("nt2011_happiness.out","w",stdout);
	scanf("%d%d",&n,&m);int cnt=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)num[i][j]=++cnt;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
		scanf("%d",&self[i][j][0]),sum+=self[i][j][0]*2;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
		scanf("%d",&self[i][j][1]),sum+=self[i][j][1]*2;
	for(int i=1;i<=n-1;i++)for(int j=1;j<=m;j++)
		scanf("%d",&row[i][j][0]),sum+=row[i][j][0]*2;
	for(int i=1;i<=n-1;i++)for(int j=1;j<=m;j++)
		scanf("%d",&row[i][j][1]),sum+=row[i][j][1]*2;
	for(int i=1;i<=n;i++)for(int j=1;j<=m-1;j++)
		scanf("%d",&line[i][j][0]),sum+=line[i][j][0]*2;
	for(int i=1;i<=n;i++)for(int j=1;j<=m-1;j++)
		scanf("%d",&line[i][j][1]),sum+=line[i][j][1]*2;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int n1=num[i][j],n2=num[i+1][j],n3=num[i][j+1];
			add(S,n1,row[i-1][j][0]+line[i][j-1][0]+row[i][j][0]+line[i][j][0]),add(n1,S,0);
			add(S,n1,self[i][j][0]*2),add(n1,S,0);
			add(n1,T,self[i][j][1]*2+row[i-1][j][1]+line[i][j-1][1]+row[i][j][1]+line[i][j][1]),add(T,n1,0);
			if(i<n)add(n1,n2,row[i][j][0]+row[i][j][1]),add(n2,n1,row[i][j][0]+row[i][j][1]);
			if(j<m)add(n1,n3,line[i][j][0]+line[i][j][1]),add(n3,n1,line[i][j][0]+line[i][j][1]);
		}
	while(bfs())ans+=dfs(S,inf);
	printf("%d",sum/2-ans/2);
}