#include<bits/stdc++.h>
using namespace std;
const int maxn=35005;
const int inf=242345425;
int m,s,t,n,num[105][105],sum,maxflow,head[maxn],dep[maxn],ctt=1;
typedef struct a{
    int next,to,w;
}per;
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
per si[maxn*10];
void add(int u,int v,int w){
    si[++ctt].next=head[u];
    si[ctt].to=v;
    si[ctt].w=w;
    head[u]=ctt;
    si[++ctt].next=head[v];
    si[ctt].to=u;
    si[ctt].w=0;
    head[v]=ctt;    
}
bool bfs(){//广搜，给每一个节点标定深度（即离起点s的距离），这里返回是否能够到达汇点t 
    memset(dep,0,sizeof(dep));
    queue<int> que;
    que.push(s);
    dep[s]=1;//可以手写队列 
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(int i=head[u];i!=-1;i=si[i].next){
            int v=si[i].to;
            if(!dep[v]&&si[i].w){//判断是否在队列中 
                dep[v]=dep[u]+1;
                que.push(v);
            }
        }
    }
    return dep[t];
}
int dfs(int u,int in){ 
    if(u==t) return in; 
    int out=0;
    for(int i=head[u];i!=-1&&in;i=si[i].next){
        int v=si[i].to;
        if(si[i].w&&dep[v]==dep[u]+1){
            int res=dfs(v,min(si[i].w,in)); 
            si[i].w-=res;
            si[i^1].w+=res;
            in-=res;
            out+=res;
        }
    }
    if(out==0) dep[u]=0;
    return out;
}
int main(){
    cin>>m>>n;
    memset(head,-1,sizeof(head)); 
    s=0,t=maxn-2;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            num[i][j]=read();
            sum+=num[i][j];
            if((i+j)&1){
                int moi=m*(i-1)+j;
                add(s,moi,num[i][j]);
                if(i>1) add(moi,m*(i-2)+j,inf);
                if(j>1) add(moi,m*(i-1)+j-1,inf);
                if(i<m) add(moi,m*i+j,inf);
                if(j<n) add(moi,m*(i-1)+j+1,inf);
            }
            else{
                add(m*(i-1)+j,t,num[i][j]);
            }
        }
    }
    while(bfs()){
        maxflow+=dfs(s,inf);
    }
    cout<<sum-maxflow;
    return 0;
} 

就是普通的最大流。91分，wa了第八个点（讨论区里好像也有好多人wa了这个点），这个点卡了什么地方啊。

12 13 489 413 874 199 180 212 137 954 888 389 263 421 191 907 277 124 443 194 33 633 388 675 767 300 700 894 843 862 270 673 646 602 561 17 422 104 268 614 826 918 802 823 158 985 811 7 251 910 496 901 807 932 97 88 534 722 933 45 478 214 365 656 708 594 847 44 339 911 870 610 871 768 133 761 409 380 753 577 737 896 267 921 55 801 10 50 680 551 435 998 790 643 768 226 78 441 349 791 574 824 458 132 163 113 775 118 1 571 281 268 971 357 345 191 204 574 785 935 583 330 686 909 52 654 334 871 677 954 45 37 442 911 680 990 766 231 400 289 695 796 839 10 560 845 293 921 65 63 858 787 598 80 346 608 516 625

ans：42550