[网络流24题#9] [cogs734] 方格取数 [网络流，最大流最小割]

将网格分为两部分，方法是黑白染色，即判断(i+j)&1即可，分开后从白色格子向黑色格子连边，每个点需要四条（边界点可能更少），也就是每个格子周围的四个方向。之后将源点和汇点分别于黑白格子连边，边权即为点权，最后用总权值减去最小割即可。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <queue>

using namespace std;

#define    INF    0x3f3f3f3f

template<const int _n,const int _m>

struct Edge

{

    struct Edge_base { int    to,next,w; }e[_m]; int    cnt,p[_n];

    Edge() { clear(); }

    void    insert(const int x,const int y,const int z)

    { e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; }

    int    start(const int x) { return p[x]; }

    void    clear() { cnt=,memset(p,,sizeof(p)); }

    Edge_base&    operator[](const int x) { return e[x]; }

};

int    n,m,N,SSS,TTT,a[][];

int    level[],cur[];

Edge<,>    e;

bool    Bfs(const int S)

{

    int    i,t;

    queue<int>    Q;

    memset(level,,sizeof(level));

    level[S]=;

    Q.push(S);

    while(!Q.empty())

    {

        t=Q.front(),Q.pop();

        for(i=e.start(t);i;i=e[i].next)

        {

            if(!level[e[i].to] && e[i].w)

            {

                level[e[i].to]=level[t]+;

                Q.push(e[i].to);

            }

        }

    }

    return level[TTT];

}

int    Dfs(const int S,const int bk)

{

    if(S==TTT)return bk;

    int    rest=bk;

    for(int &i=cur[S];i;i=e[i].next)

    {

        if(level[e[i].to]==level[S]+ && e[i].w)

        {

            int    flow=Dfs(e[i].to,min(e[i].w,rest));

            e[i].w-=flow;

            e[i^].w+=flow;

            if((rest-=flow)<=)break;

        }

    }

    if(bk==rest)level[S]=;

    return bk-rest;

}

int    Dinic()

{

    int    flow=;

    while(Bfs(SSS))

    {

        memcpy(cur,e.p,sizeof(cur));

        flow+=Dfs(SSS,0x3f3f3f3f);

    }

    return flow;

}

int main()

{

    freopen("grid.in","r",stdin);

    freopen("grid.out","w",stdout);

    int    i,j,Sum=;

    scanf("%d%d",&n,&m);

    N=n*m;SSS=N+,TTT=SSS+;

    for(i=;i<=n;++i)for(j=;j<=m;++j)

        scanf("%d",&a[i][j]),Sum+=a[i][j];

    for(i=;i<=n;++i)

    {

        for(j=;j<=m;++j)

        {

            int t=(i-)*m+j;

            if(((i&) && !(j&)) || (!(i&) && (j&)))

            {

                e.insert(SSS,t,a[i][j]);

                e.insert(t,SSS,);

                if(i>)e.insert(t,t-m,INF),e.insert(t-m,t,);

                if(i<n)e.insert(t,t+m,INF),e.insert(t+m,t,);

                if(j>)e.insert(t,t-,INF),e.insert(t-,t,);

                if(j<m)e.insert(t,t+,INF),e.insert(t+,t,);

            }

            else

            {

                e.insert(t,TTT,a[i][j]);

                e.insert(TTT,t,);

                if(i>)e.insert(t-m,t,INF),e.insert(t,t-m,);

                if(i<n)e.insert(t+m,t,INF),e.insert(t,t+m,);

                if(j>)e.insert(t-,t,INF),e.insert(t,t-,);

                if(j<m)e.insert(t+,t,INF),e.insert(t,t+,);

            }

        }

    }

    printf("%d\n",Sum-Dinic());

    return ;

}