[BZOJ2132/Luogu1935]圈地计划(网络流)

发布于 2018-02-03  61 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2132/Luogu1935]圈地计划(网络流)

Description

最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解,这块土地是一块矩形的区域,可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境,每块小区域建造商业区和工业区能取得不同的经济价值。更具体点,对于第i行第j列的区域,建造商业区将得到Aij收益,建造工业区将得到Bij收益。另外不同的区域连在一起可以得到额外的收益,即如果区域(I,j)相邻(相邻是指两个格子有公共边)有K块(显然K不超过4)类型不同于(I,j)的区域,则这块区域能增加k×Cij收益。经过Tiger.S教授的勘察,收益矩阵A,B,C都已经知道了。你能帮GDOI求出一个收益最大的方案么?

Http

BZOJ
Luogu

Tag

网络流

解决思路

最小割模型。
转化为把所有收益求和后算出最少损失,变成最小割模型。
一个格子建工业区还是商业区这个比较好处理,但若不同类型的格子相邻产生收益这不好处理。
一个格子与其相邻四个格子产生可能的收益,我们发现这个分类与黑白染色很像。
所以我们把格子黑白染色,假设白格子先选工业区,黑格子选商业区,那么相当于一开始所有的相邻不相同的收益都是可以得到的,然后再建图跑最大流。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxMap=101;
const int maxN=maxMap*maxMap*2;
const int maxM=(maxMap*maxMap*6)*2;
const int inf=2147483647;

class Edge
{
public:
    int v,flow;
};

int n,m;
int S,T;
int A[maxMap][maxMap],B[maxMap][maxMap],C[maxMap][maxMap],Id[maxMap][maxMap];
int edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
int Depth[maxN],Queue[maxN],cur[maxN];

void Add_Edge(int u,int v,int flow,int opt);
bool Bfs();
int dfs(int u,int flow);

int main()
{
    mem(Head,-1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&A[i][j]);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&B[i][j]);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&C[i][j]);
    int idcnt=0;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) Id[i][j]=++idcnt;
    S=idcnt+1;T=idcnt+2;
    int Ans=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if ((i+j)&1)//分黑白两种格子讨论
            {
                Add_Edge(S,Id[i][j],A[i][j],0);
                Add_Edge(Id[i][j],T,B[i][j],0);//先连上源汇点
                Ans+=A[i][j]+B[i][j];
                //分别讨论四个方向相邻的格子
                if (i!=1) Add_Edge(Id[i][j],Id[i-1][j],C[i][j]+C[i-1][j],1),Ans+=C[i][j]+C[i-1][j];
                if (i!=n) Add_Edge(Id[i][j],Id[i+1][j],C[i][j]+C[i+1][j],1),Ans+=C[i][j]+C[i+1][j];
                if (j!=1) Add_Edge(Id[i][j],Id[i][j-1],C[i][j]+C[i][j-1],1),Ans+=C[i][j]+C[i][j-1];
                if (j!=m) Add_Edge(Id[i][j],Id[i][j+1],C[i][j]+C[i][j+1],1),Ans+=C[i][j]+C[i][j+1];
            }
            else
            {
                Add_Edge(S,Id[i][j],B[i][j],0);
                Add_Edge(Id[i][j],T,A[i][j],0);
                Ans+=A[i][j]+B[i][j];
            }
    while (Bfs())//求最小割
    {
        for (int i=1;i<=T;i++) cur[i]=Head[i];
        while (int di=dfs(S,inf)) Ans-=di;
    }
    printf("%d\n",Ans);
    return 0;
}

void Add_Edge(int u,int v,int flow,int opt)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].v=v;E[edgecnt].flow=flow;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt].v=u;E[edgecnt].flow=opt*flow;
    return;
}

bool Bfs()
{
    mem(Depth,-1);
    int h=1,t=0;Queue[1]=S;Depth[S]=1;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((Depth[E[i].v]==-1)&&(E[i].flow>0))
                Depth[Queue[++h]=E[i].v]=Depth[u]+1;
    }
    while (t!=h);
    if (Depth[T]==-1) return 0;
    return 1;
}

int dfs(int u,int flow)
{
    if (u==T) return flow;
    for (int &i=cur[u];i!=-1;i=Next[i])
        if ((E[i].flow>0)&&(Depth[E[i].v]==Depth[u]+1))
        {
            int di=dfs(E[i].v,min(flow,E[i].flow));
            if (di)
            {
                E[i].flow-=di;
                E[i^1].flow+=di;
                return di;
            }
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2132/Luogu1935]圈地计划(网络流)


HNCJ OIer