题目大意：给你一个网格图，每个格子都有$a_{ij}$的代价和$b_{ij}$的回报，对于格子$ij$，想获得$b_{ij}$的回报，要么付出$a_{ij}$的代价，要么$ij$周围四联通的格子都付出代价，求最大的回报-代价
好神的一道题，%%%jr
想获得$b_{ij}$的回报，要么付出$a_{ij}$的代价，要么$ij$周围四联通的格子都付出代价
所以把棋盘像国际象棋一样黑白交叉染色，原图就变成了一个类似于二分图的东西
每个格子都拆成$2$个点
对于白格子，源点$S$向$W1$连流量为$a_{ij}$的边，$W1$向$W2$连流量为$b_{ij}$的边，$W2$向白格子周围四个黑格子的$B2$连流量为$inf$的边
对于黑格子，$B2$向汇点$T$连流量为$a_{ij}$的边，$B1$向$B2$连流量为$b_{ij}$的边，周围四个白格子的$W1$向$B1$连流量为$inf$的边
然后跑最大流，答案就是总回报-最大流
为什么要这么建边？我们可以对割进行分析
如果一个白格子的代价边$a_{ij}$被割掉了，说明这个格子带来的回报$\geq$代价，被归到了$T$集合里，此时流量$=$代价，统计答案时会加上回报$-$代价
如果一个白格子的代价边$a_{ij}$没被割掉，说明这个格子带来的回报$<$代价，被归到了$S$集合里，此时流量$=$回报，统计答案时会把这部分回报去掉
黑格子也是同理
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 5010
#define M1 30010
#define L1 55
using namespace std;
const int inf=0x3f3f3f3f; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
struct Edge{
int to[M1<<],nxt[M1<<],flow[M1<<],head[N1],cte;
void ae(int u,int v,int f)
{
cte++; to[cte]=v; nxt[cte]=head[u];
head[u]=cte; flow[cte]=f;
}
}e; int dep[N1],que[M1],cur[N1],n,m,hd,tl,S,T;
int bfs()
{
int x,j,v;
memset(dep,-,sizeof(dep)); memcpy(cur,e.head,sizeof(cur));
hd=,tl=; que[++tl]=S; dep[S]=;
while(hd<=tl)
{
x=que[hd++];
for(j=e.head[x];j;j=e.nxt[j])
{
v=e.to[j];
if( dep[v]==- && e.flow[j]> )
{
dep[v]=dep[x]+;
que[++tl]=v;
}
}
}
return dep[T]!=-;
}
int dfs(int x,int limit)
{
int j,v,flow,ans=;
if(!limit||x==T) return limit;
for(j=cur[x];j;j=e.nxt[j])
{
v=e.to[j]; cur[x]=j;
if( dep[v]==dep[x]+ && (flow=dfs(v,min(limit,e.flow[j]))) )
{
e.flow[j]-=flow; limit-=flow;
e.flow[j^]+=flow; ans+=flow;
if(!limit) break;
}
}
return ans;
}
int Dinic()
{
int mxflow=,j,v,ans=;
while(bfs())
mxflow+=dfs(S,inf);
return mxflow;
} int xx[]={-,,,},yy[]={,,,-};
int a[L1][L1],b[L1][L1],id[L1][L1];
inline int check(int x,int y){return (x<||y<||x>n||y>m)?:;} int main()
{
scanf("%d%d",&n,&m);
int i,j,x,y,k,tot=n*m,sum=; e.cte=; S=; T=tot+tot+;
for(i=;i<=n;i++) for(j=;j<=m;j++) a[i][j]=gint();// sum+=v[i][j];
for(i=;i<=n;i++) for(j=;j<=m;j++) b[i][j]=gint(), id[i][j]=(i-)*m+j, sum+=b[i][j];
for(i=;i<=n;i++) for(j=;j<=m;j++)
{
x=id[i][j];
if((i+j)&){
e.ae(S,x,a[i][j]); e.ae(x,S,);
e.ae(x,x+tot,b[i][j]); e.ae(x+tot,x,);
for(k=;k<;k++)
{
if(!check(i+xx[k],j+yy[k])) continue;
y=id[i+xx[k]][j+yy[k]];
e.ae(x+tot,y+tot,inf); e.ae(y+tot,x+tot,);
}
}else{
e.ae(x+tot,T,a[i][j]); e.ae(T,x+tot,);
e.ae(x,x+tot,b[i][j]); e.ae(x+tot,x,);
for(k=;k<;k++)
{
if(!check(i+xx[k],j+yy[k])) continue;
y=id[i+xx[k]][j+yy[k]];
e.ae(y,x,inf); e.ae(x,y,);
}
}
}
printf("%d\n",sum-Dinic());
return ;
}