最大和=全局和-舍弃和，而舍弃和=最小割=最大流
记为一条从u 到v 的，流量为cap 的，费用为cost 的弧与反弧
将图二染色
对于每个黑点u ，连边
对于每个白点v ，连边
对于每个黑点u ，像周围白点v 连边1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
using namespace std;
const int N=105,M=100000,INF=1<<30;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int n,m,st,ed,sum=0,w[N][N];
int cnt=0,head[N*N],d[N*N],cur[N*N];
struct edge{int to,next,flow,cap;} e[M<<1];
queue<int> Q;
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if (ch=='-') t=-1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
int F(int x,int y){return m*(x-1)+y;}
void add(int u,int v,int cap)
{
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt++].cap=cap;
}
int bfs(int s,int t)
{
while (!Q.empty()) Q.pop();
for(int i=1;i<=n*m+2;i++) d[i]=0;
d[s]=1,Q.push(s);
while (!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=head[x];~i;i=e[i].next)
{
int to=e[i].to;
if (e[i].flow<e[i].cap&&!d[to])
{
d[to]=d[x]+1;
Q.push(to);
}
}
}
return d[t];
}
int dfs(int x,int t,int flow)
{
if (!flow||x==t) return flow;
int ret=0,new_flow;
for(int &i=cur[x];~i&&flow;i=e[i].next)
{
int to=e[i].to;
if (d[x]+1==d[to])
{
new_flow=dfs(to,t,min(flow,e[i].cap-e[i].flow));
e[i].flow+=new_flow;
e[i^1].flow-=new_flow;
ret+=new_flow;
flow-=new_flow;
}
}
return ret;
}
int Dinic(int s,int t)
{
int ret=0;
while (bfs(s,t))
{
for(int i=1;i<=n*m+2;i++) cur[i]=head[i];
ret+=dfs(s,t,INF);
}
return ret;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum+=w[i][j]=read();
st=n*m+1,ed=st+1;
for(int i=1;i<=n*m+2;i++) head[i]=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if ((i+j)&1)
{
add(st,F(i,j),w[i][j]);
add(F(i,j),st,0);
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if (0<x&&x<=n&&0<y&&y<=m)
{
add(F(i,j),F(x,y),INF);
add(F(x,y),F(i,j),0);
}
}
}
else
{
add(F(i,j),ed,w[i][j]);
add(ed,F(i,j),0);
}
printf("%d\n",sum-Dinic(st,ed));
return 0;
}