先放代码,以后补充说明:

#include <cstdio>
#include <cstring>
#define M 40010
const int inf=99999999;
int gap[M],dis[M],pre[M],cur[M];
int NE,NV;
int head[M];
struct Node{
	int c,pos,next;
}E[999999];
int sap(int s,int t) {
	memset(dis,0,sizeof(int)*(NV+1));
	memset(gap,0,sizeof(int)*(NV+1));
	for(int i=0;i<NV;i++) cur[i] = head[i];
	int u = pre[s] = s,maxflow = 0,aug = -1;
	gap[0] = NV;
	while(dis[s] < NV) {
loop:		for(int &i = cur[u]; i != -1; i = E[i].next) {
				int v = E[i].pos;
				if(E[i].c && dis[u] == dis[v] + 1) {
					if(aug==-1||aug>E[i].c)aug=E[i].c;
					pre[v] = u;
					u = v;
					if(v == t) {
						maxflow += aug;
						for(u = pre[u];v != s;v = u,u = pre[u]) {
							E[cur[u]].c -= aug;
							E[cur[u]^1].c += aug;
						}
						aug = -1;
					}
					goto loop;
				}
			}
			int mindis = NV;
			for(int i = head[u]; i != -1 ; i = E[i].next) {
				int v = E[i].pos;
				if(E[i].c && mindis > dis[v]) {
					cur[u] = i;
					mindis = dis[v];
				}
			}
			if( (--gap[dis[u]]) == 0)	break;
			gap[ dis[u] = mindis+1 ] ++;
			u = pre[u];
	}
	return maxflow;
}
void Insert(int u,int v,int c,int cc = 0) {
	E[NE].c = c;	E[NE].pos = v;
	E[NE].next = head[u];	head[u] = NE++;
	E[NE].c = cc;	E[NE].pos = u;
	E[NE].next = head[v];	head[v] = NE++;
}

int main(){
	int n,m,i,j,s,t,w,sum;
	while(~scanf("%d%d",&n,&m)){
		NE=0;
		sum=0;
		s=n*m;
		t=s+1;
		NV=t+1;
		memset(head,-1,sizeof(int)*NV);
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				scanf("%d",&w);
				sum+=w;
				if((i+j)&1){
					Insert(s,i*m+j,w);
					if(i>0)
						Insert(i*m+j,(i-1)*m+j,inf);
					if(i<n-1)
						Insert(i*m+j,(i+1)*m+j,inf);
					if(j>0)
						Insert(i*m+j,i*m+j-1,inf);
					if(j<m-1)
						Insert(i*m+j,i*m+j+1,inf);
				}else{
					Insert(i*m+j,t,w);
				}
			}
		}
		printf("%dn",sum-sap(s,t));
	}
	return 0;
}