Description：

$n\times m$ 网格，每个格子有一个价值为 $v_{i,j}$ ，可以自己决定起点，第 $i$ 秒开始时可以拿走一个宝石，偶数秒的时候周围四格的宝石消失，第 $i$ 秒结束的时候可以移动，可以不动，问最多能拿到多大总价值的宝石。

$1\leqslant n,m\leqslant 100$

Solution：

就算知道了这题是网络流我也想不到，如果仔细观察一下的话会发现其实是可以选一些格子，如果某个格子选了周围四个就不能选了，因为可以不动代表可以去掉奇偶秒数的影响随意选择消除。

然后最小割就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 410

int v[MAXN][MAXN];

#define MAXP (MAXN * MAXN)

#define MAXE (MAXN * MAXN * 2 + MAXN * MAXN * 4)

struct edge

{

    int to,nxt,f;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP] = {0};

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

{//cout << a << " " << b << " " << f << endl;

    e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

    e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

    return;

}

int S,T;

int s,t;

#define INF 0x3f3f3f3f

int p[MAXN];

int ch[MAXP];

bool BFS()

{

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

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

    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(e[i].f,f - r));

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

        }

    }

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

    return r;

}

typedef long long ll;

ll dinic()

{

    ll ans = 0,r;

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

    return ans;

}

int id(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);

	ll sum = 0;

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)v[i][j] = rd();

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)sum += v[i][j];

	s = n * m + 1;t = s + 1;

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

	{

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

		{

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

			{

				add(s,id(i,j),v[i][j]);

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

				{

					int nx = i + mx[k],ny = j + my[k];

					if(1 <= nx && nx <= n && 1 <= ny && ny <= m)

					{

						add(id(i,j),id(nx,ny),INF);

					}

				}

			}

			else

			{

				add(id(i,j),t,v[i][j]);

			}

		}

	}

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

	return 0;

}