题目大意：
一个(n*m)的网格图
每个点要在文理之中选一个，选文会获得(art[i][j])的收益，选理会获得(science[i][j])的收益
如果存在某个点选的是文，而且与他相邻的格子全部选了文，会获得(sameart[i][j])的收益，如果存在某个点选的是理，而且与他相邻的格子全部选了理，会获得(samescience[i][j])的收益
求最大收益
构造最小鸽模型
每个点向源点连边，边权为(art[i][j])，向汇点连边，边权为(science[i][j])，这样满足(art)和(science)中必须鸽掉一个
然后考虑(same)的收益
我们可以考虑对每个点开两个辅助节点
一个向源点连边权为(sameart[i][j])的边，再向相邻点连(inf)边，满足必须所有相邻点的(science[i][j])边全部鸽掉才能获得
另一个向汇点连边权为(samescience[i][j])，再由相邻点向自己连(inf)边，满足必须所有相邻点的(art[i][j])边全部鸽掉才能获得
很有趣的最小割模型
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
int dx[5]={0,-1,0,1,0},dy[5]={0,0,1,0,-1};
const int inf=0x3f3f3f3f;
int n,m,sum,st,ed,ret,tot;
int val[110][110][5];
int id[110][110][3];
int head[1000010],cur[1000010],d[1000010],cnt=1;
struct point
{
int nxt,to,c;
}a[2000010];
inline void add(int x,int y,int c)
{
a[++cnt]=(point){head[x],y,c};head[x]=cnt;
a[++cnt]=(point){head[y],x,0};head[y]=cnt;
}
queue<int> q;
inline bool bfs()
{
for(int i=1;i<=tot;++i)
{
cur[i]=head[i];
d[i]=0;
}
q.push(st);d[st]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=head[now];i;i=a[i].nxt)
{
int t=a[i].to;
if(!d[t]&&a[i].c)
{
d[t]=d[now]+1;
q.push(t);
}
}
}
return d[ed];
}
inline int dfs(int now,int c)
{
if(now==ed||!c) return c;
int ret=c,f;
for(int i=cur[now];i;i=a[i].nxt)
{
cur[now]=i;
int t=a[i].to;
if(d[t]==d[now]+1)
{
f=dfs(t,min(a[i].c,ret));
if(!f) continue;
a[i].c-=f;
a[i^1].c+=f;
ret-=f;
if(!ret) return c;
}
}
if(ret==c) d[now]=0;
return c-ret;
}
inline int dinic()
{
while(bfs()) ret+=dfs(st,inf);
return ret;
}
signed main()//考虑最小割，每个点向源点连边，边权为art，向汇点连边，边权为science;
{ //处理same情况：每个点连向辅助节点，边权为inf，辅助节点边权为same-art和same-science，作为最小割
n=read(),m=read();
for(int k=1;k<=4;++k)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
val[i][j][k]=read();
sum+=val[i][j][k];
if(k==1) id[i][j][0]=++tot,id[i][j][1]=++tot,id[i][j][2]=++tot;
//如果只开一个辅助节点，原节点要和辅助节点建双向inf边
//会导致两个same全部需要割掉
}
}
}
st=++tot,ed=++tot;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
add(st,id[i][j][0],val[i][j][1]);
add(st,id[i][j][1],val[i][j][3]);
add(id[i][j][0],ed,val[i][j][2]);
add(id[i][j][2],ed,val[i][j][4]);
for(int k=0;k<=4;++k)
{
int tx=i+dx[k],ty=j+dy[k];
if(tx<1||ty<1||tx>n||ty>m) continue;
add(id[tx][ty][1],id[i][j][0],inf);
add(id[tx][ty][0],id[i][j][2],inf);
}
}
}
printf("%d
",sum-dinic());
return 0;
}