题解：AT_abc407_g [ABC407G] Domino Covering SUM

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e5+5,inf=1e18;
int s,t,head[maxn],to[maxn*2],nxt[maxn*2],val[maxn*2],tot=1,pre[maxn];
int vis[maxn],n,m,a[5005][5005],dist[maxn],flow[maxn*2],dis[maxn];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},ans,sum,cnt;
queue<int>q;
void add(int a,int b,int v,int w){
	nxt[++tot]=head[a];
	to[tot]=b;
	flow[tot]=v;
	val[tot]=w;
	head[a]=tot;
	nxt[++tot]=head[b];
	to[tot]=a;
	val[tot]=-w;
	head[b]=tot;
}
int id(int x,int y){return x*(m+1)+y;}
bool spfa(){
	for(int i=0;i<=id(n,m)+3;i++) dis[i]=inf;
	memset(vis,0,sizeof vis);
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	dist[s]=inf;
	while(!q.empty()) {
		int x=q.front();
		vis[x]=0;
		q.pop();
		for(int i=head[x];i;i=nxt[i]) {
			int y=to[i];
			if(!flow[i]) continue;
			if(dis[y]>dis[x]+val[i]) {
				dis[y]=dis[x]+val[i];
				dist[y]=min(dist[x],flow[i]);
				pre[y]=i;
				if(!vis[y]) vis[y]=1,q.push(y);
			}
		}
	}
	if(dis[t]==inf) return 0;
	return 1;
}
bool update(){
    if(dis[t]>=0) return 0;
	int x=t;
	while(x!=s){
		int id=pre[x];
		flow[id]-=dist[t];
		flow[id^1]+=dist[t];
		x=to[id^1];
	}
	ans+=dist[t];
	sum+=dis[t];
	return 1;
}
signed main(){
	int num=0;
	cin>>n>>m;
	s=id(n,m)+1,t=id(n,m)+2; 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j],num+=a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((i+j)%2==0) {
                add(s,id(i,j),1,0);
                for(int k=0;k<4;k++){
                    int nx=i+dx[k],ny=j+dy[k];
                    if (nx<1||nx>n||ny<1||ny>m) continue;
                    add(id(i,j),id(nx,ny),1,a[i][j]+a[nx][ny]);
                }
            }
			else add(id(i,j),t,1,0);
        }
    }
	while(spfa()){if(!update()) break;}
	cout<<num-sum;
	return 0;
}