又是套路啊
黑白染色，S，T连不同色的，求最小割，用总和-最小割即为答案
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <math.h>
# define ll long long
# define RG register
# define IL inline
# define Mem(a, b) memset(a, b, sizeof(a))
# define Max(a, b) (((a) > (b)) ? (a) : (b))
# define Min(a, b) (((a) < (b)) ? (a) : (b))
using namespace std;
IL int Get(){
RG char c = '!'; RG int x = 0, z;
for(; c > '9' || c < '0'; c = getchar()) z = (c == '-') ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return x * z;
}
const int INF = 2147483647, MAXN = 50001, MAXM = 2000001;
int n, m, ft[MAXN], cnt, ans, map[31][31], Q[MAXM], level[MAXN], cur[MAXN];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
struct Edge{
int to, nt, f;
} edge[MAXM];
IL void _Add(RG int u, RG int v, RG int f){
edge[cnt] = (Edge){v, ft[u], f}; ft[u] = cnt++;
edge[cnt] = (Edge){u, ft[v], 0}; ft[v] = cnt++;
}
IL void Add(RG int x, RG int y){
RG int u = (x - 1) * m + y;
for(RG int i = 0; i < 4; i++){
RG int xx = x + dx[i], yy = y + dy[i];
if(xx <= 0 || xx > n || yy <= 0 || yy > m) continue;
RG int v = (xx - 1) * m + yy;
_Add(u, v, INF);
}
}
IL int Dfs(RG int u, RG int T, RG int maxf){
if(u == T) return maxf;
RG int ret = 0;
for(RG int &e = cur[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to;
if(level[v] == level[u] + 1 && edge[e].f){
RG int f = Dfs(v, T, Min(maxf - ret, edge[e].f));
edge[e].f -= f; edge[e ^ 1].f += f;
ret += f;
if(ret == maxf) break;
}
}
return ret;
}
IL bool Bfs(RG int S, RG int T){
Mem(level, 0);
RG int head = 0, tail = 0;
Q[0] = S; level[S] = 1;
while(head <= tail){
RG int u = Q[head++];
if(u == T) return 1;
for(RG int e = ft[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to;
if(!level[v] && edge[e].f){
level[v] = level[u] + 1;
Q[++tail] = v;
}
}
}
return 0;
}
int main(){
Mem(ft, -1);
n = Get(); m = Get();
RG int S = 0, T = n * m + 1, tot = 0;
for(RG int i = 1; i <= n; i++)
for(RG int j = 1; j <= m; j++){
map[i][j] = Get(); tot += map[i][j];
if(~(i + j) & 1) _Add(S, (i - 1) * m + j, map[i][j]), Add(i, j);
else _Add((i - 1) * m + j, T, map[i][j]);
}
while(Bfs(S, T)){
for(RG int i = S; i <= T; i++)
cur[i] = ft[i];
ans += Dfs(S, T, INF);
}
printf("%d
", tot - ans);
return 0;
}