将网格分为两部分，方法是黑白染色，即判断(i+j)&1即可，分开后从白色格子向黑色格子连边，每个点需要四条（边界点可能更少），也就是每个格子周围的四个方向。之后将源点和汇点分别于黑白格子连边，边权即为点权，最后用总权值减去最小割即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define INF 0x3f3f3f3ftemplate
             
              struct Edge{ struct Edge_base { int to,next,w; }e[_m]; int cnt,p[_n]; Edge() { clear(); } void insert(const int x,const int y,const int z) { e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; } int start(const int x) { return p[x]; } void clear() { cnt=1,memset(p,0,sizeof(p)); } Edge_base& operator[](const int x) { return e[x]; }};int n,m,N,SSS,TTT,a[410][410];int level[41000],cur[41000];Edge<41000,410000> e;bool Bfs(const int S){ int i,t; queue
              
                Q; memset(level,0,sizeof(level)); level[S]=1; Q.push(S); while(!Q.empty()) { t=Q.front(),Q.pop(); for(i=e.start(t);i;i=e[i].next) { if(!level[e[i].to] && e[i].w) { level[e[i].to]=level[t]+1; Q.push(e[i].to); } } } return level[TTT];}int Dfs(const int S,const int bk){ if(S==TTT)return bk; int rest=bk; for(int &i=cur[S];i;i=e[i].next) { if(level[e[i].to]==level[S]+1 && e[i].w) { int flow=Dfs(e[i].to,min(e[i].w,rest)); e[i].w-=flow; e[i^1].w+=flow; if((rest-=flow)<=0)break; } } if(bk==rest)level[S]=0; return bk-rest;}int Dinic(){ int flow=0; while(Bfs(SSS)) { memcpy(cur,e.p,sizeof(cur)); flow+=Dfs(SSS,0x3f3f3f3f); } return flow;}int main(){ freopen("grid.in","r",stdin); freopen("grid.out","w",stdout); int i,j,Sum=0; scanf("%d%d",&n,&m); N=n*m;SSS=N+1,TTT=SSS+1; for(i=1;i<=n;++i)for(j=1;j<=m;++j) scanf("%d",&a[i][j]),Sum+=a[i][j]; for(i=1;i<=n;++i) { for(j=1;j<=m;++j) { int t=(i-1)*m+j; if(((i&1) && !(j&1)) || (!(i&1) && (j&1))) { e.insert(SSS,t,a[i][j]); e.insert(t,SSS,0); if(i>1)e.insert(t,t-m,INF),e.insert(t-m,t,0); if(i
               
                1)e.insert(t,t-1,INF),e.insert(t-1,t,0); if(j
                
                 1)e.insert(t-m,t,INF),e.insert(t,t-m,0); if(i
                 
                  1)e.insert(t-1,t,INF),e.insert(t,t-1,0); if(j