Description：

$N\times M$ 的网格图，控制每个点有 $a[i][j]$ 的代价，如果他被控制了或者他周围四个都被控制了，那么就可以获得 $b[i][j]$ 的收益，最大化收益 $-$ 代价。

$1\le N,M\le 50$

Solution：

一个格子有 $3$ 种可能，放弃它，控制他，控制他周围四个点，这题看上去就是一个最小割，但是建图非常神奇。

首先把网格图黑白染色，根据最小割的原理，应该是先把所有收益加起来 $-$ 最小割，如果放弃它，那么就应该割掉一条边权为 $b[i][j]$ 的边；如果控制他，那么就应该割掉一条边权为 $a[i][j]$ 的边，如果他四周都被控制了，那么应该四周都选，直接说建图，把每个白点拆成两个点放在左边，把每个黑点拆成两个点放在右边，构成了一个四分图，源点朝第一个白点连容量为 $a[i][j]$ 的边，如果割掉这条边就代表放弃它，第一个白点向第二个白点连容量为 $b[i][j]$ 的边，代表控制他，第一个黑点朝第二个黑点连容量 $b[i][j]$ 的边，第二个黑点朝汇点连容量 $a[i][j]$ 的边，这样只要处理第三种情况就好了，对于一个白点，如果选三那么周围必须都是黑点，那么就把第二个白点朝第二个黑点连容量 $+\infty$ 的边，因为如果前两个都没被割的话，那只能割掉周围四个的 $a[i][j]$ ，对于黑点的情况，也应把他周围四个白点的一号点和他的一号点连容量 $+\infty$ 的边，这样要么放弃黑点，要么控制黑点，要么买下四个白点。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 55

int cst[MAXN][MAXN];

int val[MAXN][MAXN];

#define INF 0x3f3f3f3f

int s,t;

struct edge

{

	int to,nxt,f;

}e[MAXN * MAXN * 6 * 2];

int edgenum = 0;

int lin[MAXN * MAXN * 2];

void add(int a,int b,int f)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int ch[MAXN * MAXN * 2];

bool BFS()

{

	queue<int> q;q.push(s);

	memset(ch,-1,sizeof(ch));ch[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(ch[e[i].to] == -1 && e[i].f)

			{

				ch[e[i].to] = ch[k] + 1;

				q.push(e[i].to);

			}

		}

	}

	return (ch[t] != -1);

}

int flow(int k,int f)

{

	if(k == t)return f;

	int r = 0;

	for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

	{

		if(ch[e[i].to] == ch[k] + 1 && e[i].f)

		{

			int l = flow(e[i].to,min(f - r,e[i].f));

			e[i].f -= l;r += l;e[i ^ 1].f += l;

		}

	}

	if(r == 0)ch[k] = -1;

	return r;

}

int dinic()

{

	int ans = 0,r;

	while(BFS())while(r = flow(s,INF))ans += r;

	return ans;

}

int to(int i,int j){return (i - 1) * m + j;}

int mx[4] = {0,0,-1,1};

int my[4] = {1,-1,0,0};

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			scanf("%d",&cst[i][j]);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			scanf("%d",&val[i][j]);

	s = 0;t = 1;

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			ans += val[i][j];

			if((i + j) % 2 == 0)

			{

				add(s,to(i,j) << 1,cst[i][j]);

				add(to(i,j) << 1,to(i,j) << 1 | 1,val[i][j]);

				for(int k = 0;k < 4;++k)

				{

					if(i + mx[k] >= 1 && i + mx[k] <= n && j + my[k] >= 1 && j + my[k] <= m)

					{

						add(to(i,j) << 1 | 1,to(i + mx[k],j + my[k]) << 1 | 1,INF);

					}

				}

			}

			else

			{

				add(to(i,j) << 1 | 1,t,cst[i][j]);

				add(to(i,j) << 1,to(i,j) << 1 | 1,val[i][j]);

				for(int k = 0;k < 4;++k)

				{

					if(i + mx[k] >= 1 && i + mx[k] <= n && j + my[k] >= 1 && j + my[k] <= m)

					{

						add(to(i + mx[k],j + my[k]) << 1,to(i,j) << 1,INF);

					}

				}

			}

		}

	}

	cout << ans - dinic() << endl;

	return 0;

}