【BZOJ2132】圈地计划（最小割）

题面

BZOJ

题解

对我而言，不可做！！！

所以我膜烂了ZSY大佬

他的博客写了怎么做。。。

这，，。。。太强啦！！

完全想不到黑白染色之后反着连边

然后强行把同侧转化成异侧求最小割。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAXL 500000

#define MAX 50000

#define INF 1000000000

#define MAXN 120

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line

{

    int v,next,w;

}e[MAXL];

int h[MAX],cnt;

int S,T,n,m,K;

inline void Add(int u,int v,int w)

{

    e[cnt]=(Line){v,h[u],w};h[u]=cnt++;

    e[cnt]=(Line){u,h[v],0};h[v]=cnt++;

}

inline void Add2(int u,int v,int w)

{

    e[cnt]=(Line){v,h[u],w};h[u]=cnt++;

    e[cnt]=(Line){u,h[v],w};h[v]=cnt++;

}

int level[MAX];

bool BFS()

{

    memset(level,0,sizeof(level));

    level[S]=1;

    queue<int> Q;

    Q.push(S);

    while(!Q.empty())

    {

        int u=Q.front();Q.pop();

        for(int i=h[u];i!=-1;i=e[i].next)

        {

            int v=e[i].v;

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

                level[v]=level[u]+1,Q.push(v);

        }

    }

    return level[T];

}

int DFS(int u,int flow)

{

    if(flow==0||u==T)return flow;

    int ret=0;

    for(int i=h[u];i!=-1;i=e[i].next)

    {

        int v=e[i].v;

        if(e[i].w&&level[v]==level[u]+1)

        {

            int dd=DFS(v,min(flow,e[i].w));

            flow-=dd;ret+=dd;

            e[i].w-=dd;e[i^1].w+=dd;

        }

    }

	if(!ret)level[u]=0;

    return ret;

}

int Dinic()

{

    int ret=0;

    while(BFS())ret+=DFS(S,INF);

    return ret;

}

int g[MAXN][MAXN],tot=1,ans;

int A[MAXN][MAXN],B[MAXN][MAXN],C[MAXN][MAXN];

int main()

{

	memset(h,-1,sizeof(h));

	n=read();m=read();

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

		for(int j=1;j<=m;++j)g[i][j]=++tot;

	S=0;T=tot+1;

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

		for(int j=1;j<=m;++j)ans+=A[i][j]=read();

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

		for(int j=1;j<=m;++j)ans+=B[i][j]=read();

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

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

		{

			C[i][j]=read();

			if(i!=1)ans+=C[i][j];

			if(j!=1)ans+=C[i][j];

			if(i!=n)ans+=C[i][j];

			if(j!=m)ans+=C[i][j];

		}

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

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

		{

			if((i+j)&1)

			{

				Add(S,g[i][j],A[i][j]);

				Add(g[i][j],T,B[i][j]);

				if(i!=1)Add2(g[i][j],g[i-1][j],C[i][j]+C[i-1][j]);

				if(j!=1)Add2(g[i][j],g[i][j-1],C[i][j]+C[i][j-1]);

				if(i!=n)Add2(g[i][j],g[i+1][j],C[i][j]+C[i+1][j]);

				if(j!=m)Add2(g[i][j],g[i][j+1],C[i][j]+C[i][j+1]);

			}

			else Add(g[i][j],T,A[i][j]),Add(S,g[i][j],B[i][j]);

		}

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

	return 0;

}