题目描述：
小N手上有一个N*M的方格图，控制某一个点要付出Aij的代价，然后某个点如果被控制了，或者他周围的所有点(上下左右)都被控制了，那么他就算是被选择了的。一个点如果被选择了，那么可以得到Bij的回报，现在请你帮小N选一个最优的方案，使得回报-代价尽可能大。
题解：
最开始以为是最大权闭合子图裸题，后来发现少了点什么……
一般的图是正权->负权，但是这道题是负权->正权。
于是考虑拆点+最小割。
先假设手里拿着有所有的价值，即$\sum(b)$
对于一个点有三种情况：
1.占领这个点，此时代价为$a$；
2.不占领这个点，但是上下左右的某一个格子被占领了，此时代价为$0$；
2.不占领这个点，而且上下左右都是空的，此时代价为$b$；
我们可以先将棋盘黑白染色，然后建图。
重点是怎么建图。
拆点，每个点拆出的$x,y$之间连一条容量为$b$的边，源点向黑点的$x$连容量为$a$的边，白点的$y$向汇点连一条容量为$a$的边。
黑$x$向附近的白$x$连容量为$inf$的边，$y$同理。
意思是强迫割掉$a$，$b$或相邻点的$a$。
代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 5500;
const int inf = 0x3f3f3f3f;
template<typename T>
inline void read(T&x)
{
T f = 1,c = 0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
x = f*c;
}
int n,m,hed[N],cnt=-1,S=1,T,cur[N];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
bool check(int x,int y){return x>=1&&y>=1&&x<=n&&y<=m;}
int _id(int x,int y){return (x-1)*m+y;}
ll ans;
struct EG
{
int to,nxt;
ll w;
}e[20*N];
void ae(int f,int t,ll w)
{
e[++cnt].to = t;
e[cnt].nxt = hed[f];
e[cnt].w = w;
hed[f] = cnt;
}
void AE(int f,int t,ll w)
{
ae(f,t,w);
ae(t,f,0);
}
int dep[N];
bool vis[N];
bool bfs()
{
memset(dep,0x3f,sizeof(dep));
memcpy(cur,hed,sizeof(cur));
queue<int>q;
dep[1]=0,vis[1]=1;q.push(1);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int j=hed[u];~j;j=e[j].nxt)
{
int to = e[j].to;
if(e[j].w&&dep[to]>dep[u]+1)
{
dep[to]=dep[u]+1;
if(!vis[to])vis[to]=1,q.push(to);
}
}
vis[u]=0;
}
return dep[T]!=inf;
}
ll dfs(int u,ll lim)
{
if(u==T||!lim)return lim;
ll fl=0,f;
for(int j=cur[u];~j;j=e[j].nxt)
{
cur[u]=j;
int to = e[j].to;
if(dep[to]==dep[u]+1&&(f=dfs(to,min(lim,e[j].w))))
{
fl+=f,lim-=f;
e[j].w-=f,e[j^1].w+=f;
if(!lim)break;
}
}
return fl;
}
ll dinic()
{
ll ret=0;
while(bfs())
ret+=dfs(S,inf);
return ret;
}
int main()
{
read(n),read(m);
if(n==1&&m==1)
{
int a,b;
read(a),read(b);
if(b>a)ans=b-a;
printf("%lld\n",ans);
return 0;
}
memset(hed,-1,sizeof(hed));
for(int i=1;i<=n;i++)
for(int a,j=1;j<=m;j++)
{
read(a);
if((i+j)&1)AE(S,_id(i,j)<<1,a);
else AE(_id(i,j)<<1|1,T,a);
}
for(int i=1;i<=n;i++)
for(int b,j=1;j<=m;j++)
{
read(b);ans+=b;
int u = _id(i,j);
AE(u<<1,u<<1|1,b);
if((i+j)&1)
{
for(int x,y,o=0;o<4;o++)
{
x = dx[o]+i,y = dy[o]+j;
if(check(x,y))
{
int t = _id(x,y);
AE(u<<1,t<<1,inf);
AE(u<<1|1,t<<1|1,inf);
}
}
}
}
printf("%lld\n",ans-dinic());
return 0;
}