【网络流/最小割】方格取数问题

题目描述
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

输入格式
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。

对于相邻的方格，横纵坐标之和奇偶性不同，那么将其分成两部分，形成二分图，求最小割即踢掉不符合条件的最小的数和，奇偶两部分分别连汇点和源点，边权为方格内的数，而两部分之间的边权取INF，保证割掉的是两个点之一的边权。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
const int maxn=1e4+5;
const int maxm=1e5+5;
const int INF=0x3f3f3f3f;
using namespace std;
struct node
{
    int ver[maxm],nex[maxm],f[maxm],head[maxn],dep[maxn],cur[maxn];
    int src,sink,tot,n;
    ll ant;
    void add(int u,int v,int flow)
    {
        ver[++tot]=v;
        nex[tot]=head[u];
        f[tot]=flow;
        head[u]=tot;
        ver[++tot]=u;
        nex[tot]=head[v];
        f[tot]=0;
        head[v]=tot;
    }
    bool bfs()
    {
        queue<int> q;
        memset(dep,-1,sizeof dep);
        dep[src]=0;
        q.push(src);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int i=head[u];i;i=nex[i])
            {
                int v=ver[i];
                if(dep[v]==-1&&f[i])
                {
                    dep[v]=dep[u]+1;
                    if(v==sink)
                        return true;
                    q.push(v);
                }
            }
        }
        return false;
    }
    int dfs(int u,int mx)
    {
        if(u==sink)
            return mx;
        for(int &i=cur[u];i;i=nex[i])
        {
            int v=ver[i];
            if(dep[v]==dep[u]+1&&f[i]>0)
            {
                int flow=dfs(v,min(mx,f[i]));
                if(flow)
                {
                    f[i]-=flow;
                    f[i^1]+=flow;
                    return flow;
                }
            }
        }
        return 0;
    }
    ll dinic(int s,int t)
    {
        this->src=s;
        this->sink=t;
        ant=0;
        while(bfs())
        {
            for(int i=0;i<=n;i++)
            {
                cur[i]=head[i];
            }
            while(int d=dfs(src,INF))
            {
                ant+=d;
            }
        }
        return ant;
    }
    void init(int n)
    {
        this->n=n;
        memset(head,0,sizeof head);
        tot=1;
    }
}G;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main()
{
    int n,m,s,t;
    scanf("%d %d",&n,&m);
    s=n*m+1;
    t=n*m+2;
    ll ant=0;
    G.init(t+5);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            ant+=x;
            if((i+j)&1)
            {
                G.add(s,(i-1)*m+j,x);
            }
            else
            {
                G.add((i-1)*m+j,t,x);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if((i+j)&1)
            {
                for(int k=0;k<4;k++)
                {
                    int ni=i+dx[k];
                    int nj=j+dy[k];
                    if(ni<1||ni>n||nj<1||nj>m)
                        continue;
                    G.add((i-1)*m+j,(ni-1)*m+nj,INF);
                }
            }
        }
    }
    ant-=G.dinic(n*m+1,n*m+2);
    printf("%lld\n",ant);
    return 0;
}