题目链接：传送门
这道题要求取不相邻的数字让和最大。我们不防反面考虑。考虑在全部联通时选多少数可以将次图断开，让源点汇点不连通，并且使数的和最小，所以答案为数字总和-选的数字和。
相邻的数字只能选一个，所以我们将这个表格染色,将这个图染成黑白棋盘:
我们将所有的黑点和源点相连接，流为当前格子的值，将所有的白点和所有的汇点相连接，流为当前格子的值。在将所有的黑点和所有相邻的白点相连，流量为inf，注意判断界限！！！！。
所以为了满足条件要保证没有一条边由源点-->黑点-->白点-->汇点的路径，所以不难看出是最小割了，前面说了答案为数字总和-选的数字和。
所以直接跑最小割就好了
#include<bits/stdc++.h>
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define rg register
using namespace std;
typedef long long ll;
int n,m,s,t,z,y,x;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f= (c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
struct node{
int to,next,v;
}a[200001];
int cnt,head[200001],cur[200001];
void add(int x,int y,int c){
a[++cnt].to=y;
a[cnt].next=head[x];
a[cnt].v=c;
head[x]=cnt;
}
queue <int> q;
int dep[10001];
int bfs(){
memset(dep,0,sizeof(dep));
q.push(s),dep[s]=1;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i;i=a[i].next){
int v=a[i].to;
if(!dep[v]&&a[i].v)
q.push(v),dep[v]=dep[now]+1;
}
}
if(dep[t]!=0)
return 1;
else
return 0;
}
int dfs(int k,int list){
if(k==t)
return list;
for(int & i=cur[k];i;i=a[i].next){
int v=a[i].to;
if(a[i].v&&dep[v]==dep[k]+1){
int p=dfs(v,min(list,a[i].v));
if(p){
a[i].v-=p;
if(i%2)
a[i+1].v+=p;
else
a[i-1].v+=p;
return p;
}
}
}
return 0;
}
int Dinic(){
int ans=0;
while(bfs()){
for(int i=0;i<t;i++)
cur[i]=head[i];
int k=dfs(s,2147483);
while(k)
ans+=k,k=dfs(s,2147483);
}
return ans;
}
int f[101][101];
int fx[6]={0,0,0,-1,1};
int fy[6]={0,1,-1,0,0};
int main(){
n=read(),m=read(),s=0,t=n*m+1;
int sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
x=read(),sum+=x;
if(((i+j)%2)==0)
add((i-1)*m+j,t,x),add(t,(i-1)*m+j,0);
else
add(s,(i-1)*m+j,x),add((i-1)*m+j,s,0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=4;k++){
int x=i+fx[k],y=j+fy[k],p=(x-1)*m+y;
if(x>0&&y>0&&x<=n&&y<=m&&((i+j)%2)==1)
add((i-1)*m+j,p,10000000),add(p,(i-1)*m+j,0);
}
int ans=Dinic();
printf("%d",sum-ans);
}