C++ 解法, 执行用时: 5ms, 内存消耗: 528K, 提交时间: 2022-01-30 13:32:17

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 10100,M = 1e6+10,inf=0x3f3f3f;
int h[N],ne[M],e[M],f[M],idx;
void add(int a,int b,int c){
    ne[idx] = h[a],e[idx] = b,f[idx] = c,h[a] = idx++;
    ne[idx] = h[b],e[idx] = a,f[idx] = 0,h[b] = idx++;
}
int pre[N],a[N];
int EK(int s,int t){
    int flow = 0;
    while(1){
        memset(a,0,sizeof a);
        queue<int> q;
        q.push(s);
        a[s] = inf;
        while(!q.empty()){
            int u = q.front();q.pop();
            for(int i = h[u];~i;i=ne[i]){
                int y = e[i];
                if(f[i] > 0 && !a[y]){
                    a[y] = min(a[u],f[i]);
                    pre[y] = i;
                    q.push(y);
                }
            }
            if(a[t])break;
        }
        if(!a[t])break;
        for(int i = t;i!=s;i=e[pre[i]^1]){
            f[pre[i]] -= a[t];
            f[pre[i]^1] += a[t];
        }
        flow += a[t];
    }
    return flow;
}
int n,m;
int main(){
    int tp,s = 0,t=1,sum=0;
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin >> tp;
            sum+=tp;
            if((i+j)&1){
                add(s,i*m+j,tp);
                if(i - 1 >= 1)add(i*m+j,(i-1)*m+j,inf);
                if(i + 1 <= n)add(i*m+j,(i+1)*m+j,inf);
                if(j - 1 >= 1)add(i*m+j,i*m+j-1,inf);
                if(j + 1 <= m)add(i*m+j,i*m+j+1,inf);
            }else{
                add(i*m+j,t,tp);
            }
        }
    }
    cout << sum - EK(s,t) << endl;
    return 0;
}