题意

在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。

---

想法

我们将问题转化为：一开始所有格子都选，之后去掉价值和最少的一些格子使剩下的格子合法。

将方格黑白染色，白格子连向S，黑格子连向T，边权为这个格子的值（也就是说将格子转移到边上）。

相邻的黑白格子间连INF的边。（这样每条从S到T的路径都为 S->白格子->黑格子->T ， 这两个格子不能同时选，S->白格子 与 黑格子->T 间必然会割掉一条边）

注意一个小trick:对于永远不被割掉的边，边权设为INF

这样跑完最小割后，剩下的格子是合法的。而最小割的容量便为去掉的那些格子的价值和。

---

代码

#include
    
     #include
     
      #include
      
       #define INF 2000000000using namespace std;typedef long long ll;const int N = 10005;struct node{    int v,f;    node *next,*rev;       }pool[N*20],*h[N];int cnt;void addedge(int u,int v,int f){    node *p=&pool[++cnt],*q=&pool[++cnt];    p->v=v;p->next=h[u];h[u]=p; p->f=f;p->rev=q;    q->v=u;q->next=h[v];h[v]=q; q->f=0;q->rev=p;     }int S,T;int que[N],level[N];bool bfs(){    int head=0,tail=0,u,v;    for(int i=S;i<=T;i++) level[i]=-1;    level[S]=1; que[tail++]=S;    while(head
       
        next)            if(p->f && level[v=p->v]==-1){                level[v]=level[u]+1;                que[tail++]=v;                    }        if(level[T]!=-1) return true;    }         return false;}int find(int u,int f){    int v,s=0,t;    if(u==T) return f;    for(node *p=h[u];p;p=p->next)        if(p->f && s
        
         v]==level[u]+1){            t=find(v,min(f-s,p->f));            if(t){                s+=t;                p->f-=t;                p->rev->f+=t;                  }        }    if(!s) level[u]=-1;    return s;}ll dinic(){    ll f=0;    while(bfs()) f+=find(S,INF);    return f;}int n,m;int val[105][105];bool check(int x,int y){    if(x<1 || y<1 || x>n || y>m) return false;    return true;     }int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++) scanf("%d",&val[i][j]);            ll sum=0;    S=0; T=n*m+1;    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++){            sum=sum+val[i][j];            if((i+j)&1) addedge(S,(i-1)*m+j,val[i][j]);            else{                addedge((i-1)*m+j,T,val[i][j]);                continue;                 }            for(int dx=-1;dx<2;dx++)                for(int dy=-1;dy<2;dy++)                    if(dx*dy==0 && dx!=dy){                        int t1=i+dx,t2=j+dy;                        if(check(t1,t2)) addedge((i-1)*m+j,(t1-1)*m+t2,INF);                               }        }        sum-=dinic();    printf("%lld\n",sum);        return 0;    }