这是一道最小割转最大流的例题。
首先，我们发现，这一题要求我们求的是所取和。然后容易知道，所取和等于总和减去舍弃和。
故而，我们要使得所取和最大，就只需要使得舍弃和最小。
尝试用所取和来建图并且跑最大流，发现，它并不是那么容易地建成一个可靠的图。
正难则反，我们考虑怎么样才能让舍弃和最小。
于是尝试用舍弃和最小来建图并且跑最小割。观察题目的性质我们发现，所有的坐标和的奇偶性相同的方格，永远是互不影响的。
这启发我们建一个二分图。
我们不妨将奇点建在左侧，偶点建在右侧。然后从源点向奇点连容量为数值的边；从偶点向汇点连容量为数值的边。
于是，很显然，当我们割掉任何一条边的时候，就意味着相应的点是不取的。
接着我们将相邻的黑白点连容量为无穷大的边，这意味着这两个点之间至少有一个不能取。
然后跑最大流得到最小割即可。
#include<iostream>
#include<cstdio>
#include<queue>
const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f;
inline int Min(int A,int B){
return A<B?A:B;
}
struct ee{
int v;
int w;
int nxt;
}e[200005];
int h[40005],et=-1;
int dep[40005],nw[40005];
inline void Eadd(int U,int V,int W){
e[++et]=(ee){V,W,h[U]};
h[U]=et;
}
inline void add(int U,int V,int W){
Eadd(U,V,W);
Eadd(V,U,0);
}
int n,m,s,t;
inline int calc(int X,int Y){
return (X-1)*m+Y;
}
std::queue<int> q;
inline bool bfs(){
for(int i=1;i<=t;++i){
dep[i]=INF;
nw[i]=h[i];
}
while(!q.empty()){
q.pop();
}
dep[s]=0;
q.push(s);
int p;
while(!q.empty()){
p=q.front();
q.pop();
for(int i=h[p];i>=0;i=e[i].nxt){
if(dep[e[i].v]==INF&&e[i].w){
dep[e[i].v]=dep[p]+1;
q.push(e[i].v);
}
}
}
return dep[t]<INF;
}
inline int dfs(int X,int V){
if(!V||X==t){
return V;
}
int cnt=0,val;
for(int i=nw[X];i>=0;i=e[i].nxt){
nw[X]=i;
if(dep[e[i].v]==dep[X]+1){
val=dfs(e[i].v,Min(e[i].w,V));
if(val){
V-=val;
cnt+=val;
e[i].w-=val;
e[i^1].w+=val;
if(!V){
break;
}
}
}
}
return cnt;
}
inline int dinic(){
int ans=0;
while(bfs()){
ans+=dfs(s,INF);
}
return ans;
}
void init(){
scanf("%d%d",&n,&m);
s=n*m+1,t=n*m+2;
for(int i=1;i<=t;++i){
h[i]=-1;
}
int x,cnt=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&x);
cnt+=x;
if((i+j)&1){
add(s,calc(i,j),x);
if(i+1<=n){
add(calc(i,j),calc(i+1,j),VERYBIG);
}
if(i-1>=1){
add(calc(i,j),calc(i-1,j),VERYBIG);
}
if(j+1<=m){
add(calc(i,j),calc(i,j+1),VERYBIG);
}
if(j-1>=1){
add(calc(i,j),calc(i,j-1),VERYBIG);
}
}else{
add(calc(i,j),t,x);
}
}
}
printf("%d\n",cnt-dinic());
}
int main(){
init();
return 0;
}