在一个有 $m*n$ 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 $2$ 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

第 1 行有 2 个正整数 $m$ 和 $n$，分别表示棋盘的行数和列数。接下来的 $m$ 行，每行有 $n$ 个正整数，表示棋盘方格中的数。

程序运行结束时，将取数的最大总和输出。

思路

把每个格子看做一个点，向相邻的四个格子连边。当前的格子和四周的格子互斥。要让每个格子不与相邻的格子同时选，就是切断它们之间的边。切断边数的最小值就是最小割。

不需要的边割掉后，剩下的就是答案。

把格子黑白相间染色，源点向每一个黑格（或白格）$i$ 连权值为 $a[i]$ 的边，每一个白格（或黑格）$i$ 向汇点连权值为 $a[i]$ 的边，每个黑格（或白格）向相邻的格子连权值为 $+ \infty$ 的边。

跑一遍 Dinic，得到最小割（最大流）为 $ans$，答案即为 $\sum_i\sum_ja\lbrack i\rbrack\lbrack j\rbrack-ans$。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005],d[200005];
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
bool bfs(long long S,long long T){
    memset(v,0,sizeof(v));
    memset(d,63,sizeof(d));
    queue<long long> q;
    q.push(S);
    v[S]=1;
    d[S]=0;
    while (!q.empty()){
        long long now=q.front();
        q.pop();
        v[now]=0;
        for (int i=last[now];i;i=nextt[i]){
            int j=to[i];
            if (d[j]>d[now]&&s[i]){
            	d[j]=d[now]+1;
            	if (!v[j]){
	            	q.push(j);
	            	v[j]=1;
				}
			}
        }
    }
    if (d[T]<1000000000){
    	return 1;
	}
    return 0;
}
int dfs(long long x,long long minn,long long T){
	if (x==T){
		return minn;
	}
	int tmp=0;
	for (int i=last[x];i;i=nextt[i]){
        int j=to[i];
        if (d[j]==d[x]+1&&s[i]){
			tmp=dfs(j,min(minn,s[i]),T);
			if (tmp){
	            s[i]-=tmp;
	            s[i^1]+=tmp;
	            return tmp;
			}
		}
    }
    return 0;
}
long long dinic(long long S,long long T){
	long long ans=0,tmp=0;
	while (bfs(S,T)){
		while (1){
			tmp=dfs(S,2147483647,T);
			if (!tmp){
				break;
			}
			ans+=tmp;
		}
	}
    return ans;
}
inline int calc(int x,int y){
	return (x-1)*m+y;
}
int main(){
    long long S=10005,T=10006;
    cin>>n>>m;
    int sum=0;
    int a[105][105];
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=m;j++){
    		cin>>a[i][j];
    		sum+=a[i][j];
    		if ((i+j)%2==1){
    			add(S,calc(i,j),a[i][j]);
    			add(calc(i,j),S,0);
			}
			if ((i+j)%2==0){
				add(calc(i,j),T,a[i][j]);
				add(T,calc(i,j),0);
			}
		}
	}
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=m;j++){
    		if ((i+j)%2==1){
    			if (i>1){
	    			add(calc(i,j),calc(i-1,j),19260817);
	    			add(calc(i-1,j),calc(i,j),0);
				}
    			if (i<n){
	    			add(calc(i,j),calc(i+1,j),19260817);
	    			add(calc(i+1,j),calc(i,j),0);
				}
    			if (j>1){
	    			add(calc(i,j),calc(i,j-1),19260817);
	    			add(calc(i,j-1),calc(i,j),0);
				}
    			if (j<m){
	    			add(calc(i,j),calc(i,j+1),19260817);
	    			add(calc(i,j+1),calc(i,j),0);
				}
			}
		}
	}
    bfs(S,T);
    cout<<sum-dinic(S,T);
}