```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=1e18+10;
int n,m;
int head[1000010],ver[1000010],nex[1000010],edge[1000010];
int tot;
int d[1000010],now[1000010];
int s,t,allv,maxflow;
int mp[1010][1010];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int get(int x,int y)
{
return (x-1)*m+y;
}
bool check(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=m;
}
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z,nex[tot]=head[x],head[x]=tot;
ver[++tot]=x,edge[tot]=0,nex[tot]=head[y],head[y]=tot;
}
queue<int>q;
bool bfs()
{
memset(d,0,sizeof(d));
while(q.size())q.pop();
d[s]=1,now[s]=head[s];
q.push(s);
while(q.size())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=nex[i])
{
int y=ver[i];
if(!d[y]&&edge[i])
{
d[y]=d[x]+1;
now[y]=head[y];
q.push(y);
if(y==t)return 1;
}
}
}
return 0;
}
int dinic(int x,int flow)
{
if(x==t)return flow;
int rest=flow;
int i,k;
for(i=now[x];i;i=nex[i])
{
int y=ver[i];
if(edge[i]&&d[y]==d[x]+1)
{
k=dinic(y,min(rest,edge[i]));
if(!k)d[y]=0;
edge[i]-=k;
edge[i^1]+=k;
rest-=k;
}
}
now[x]=i;
return flow-rest;
}
signed main()
{
scanf("%lld%lld",&n,&m);s=n*m+1,t=n*m+2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%lld",&mp[i][j]),allv+=mp[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if((i+j)%2==1)
{
add(s,get(i,j),mp[i][j]);
for(int k=0;k<4;k++)
{
int nowx=i+dx[k],nowy=j+dy[k];
if(check(nowx,nowy))
add(get(i,j),get(nowx,nowy),INF);
}
}
else add(get(i,j),t,mp[i][j]);
}
int flow=0;
while(bfs())
while(flow=dinic(s,INF))maxflow+=flow;
printf("%lld\n",allv-maxflow);
}
```
by husy @ 2022-10-13 17:57:15
tot=1
by EricKong @ 2022-10-13 18:55:54
[ac link](https://www.luogu.com.cn/record/89715500)
by EricKong @ 2022-10-13 18:56:29
@[EricKong](/user/332029) OK谢谢
此帖终
by husy @ 2022-10-13 19:21:04