方格取数问题

可以看出原图是一个二分图
调用最大独立集模板即可

#include<bits/stdc++.h>
using namespace std;
const int N=10005,M=20005,inf=1000000;
int n,m,S,T;
int get(int x,int y){
    return x*m+y-1;
}
int fb(int x,int y){
    return (x+y)&1;
}
struct oppo{
    int to,nex,s;
}rod[M];
int head[N],tot;
void add(int from,int to,int s)
{
    rod[tot].to=to;
    rod[tot].s=s;
    rod[tot].nex=head[from];
    head[from]=tot++;
}
void link(int from,int to,int s)
{
    add(from,to,s);
    add(to,from,0);
}
int ans;
int d[N],cur[N];
bool bfs()
{
    queue< int > v;
    memset(d,-1,sizeof(d));
    d[S]=0,cur[S]=head[S];
    v.push(S);
    while(v.size()){
        int lxl=v.front();v.pop();
        for(int i=head[lxl];~i;i=rod[i].nex){
            int to=rod[i].to;
            if(d[to]==-1&&rod[i].s){
                d[to]=d[lxl]+1;
                cur[to]=head[to];
                if(to==T) return 1;
                v.push(to);
            }
        }
    }
    return 0;
}
int find(int x,int low)
{
    if(x==T) return low;
    int all=0;
    for(int i=cur[x];~i;i=rod[i].nex){
        cur[x]=i;
        int to=rod[i].to;
        if(d[to]==d[x]+1&&rod[i].s){
            int t=find(to,min(rod[i].s,low-all));
            if(!t) d[to]=-1;
            rod[i].s-=t;
            rod[i^1].s+=t;
            all+=t;
        }
        if(all==low) break;
    }
    return all;
}
int dinic()
{
    int ans=0,r;
    while(bfs()) while(r=find(S,inf)) ans+=r;
    return ans;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    S=0,T=get(n,m)+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int t;
            scanf("%d",&t);
            ans+=t;
            if(fb(i,j)){
                link(S,get(i,j),t);
                if(i!=n) link(get(i,j),get(i+1,j),inf);
                if(i!=1) link(get(i,j),get(i-1,j),inf);
                if(j!=m) link(get(i,j),get(i,j+1),inf);
                if(j!=1) link(get(i,j),get(i,j-1),inf);
            } 
            else link(get(i,j),T,t);
        }
    cout<<ans-dinic()<<"\n";
    return 0;
}