[GDKOI2010] 圈地计划(网络流)

题2链接：https://www.luogu.org/problemnew/show/P1935

Description

最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。

题1
另外同种的区域连在一起可以得到额外的收益，即如果相邻有K块（显然K不超过4）同种类型的区域，则这块区域能增加k×Cij收益。

上面注意是相同的区域可获得收益，而下面的是不同的区域可获得收益

题2
另外不同的区域连在一起可以得到额外的收益，即如果区域(I,j)相邻（相邻是指两个格子有公共边）有K块（显然K不超过4）类型不同于(I,j)的区域，则这块区域能增加k×Cij收益。

经过Tiger.S教授的勘察，收益矩阵A,B,C都已经知道了。你能帮GDOI求出一个收益最大的方案么？

我们首先看T1

仔细看题，对于每一块区域我们要选择它是商业区还是工业区。嗯？分成两个？在考虑若是所有的c数组不论该点选怎么都能产生贡献，我们最后减去最小的多算的贡献就好了。

注意这所谓最小的贡献必须建立在每一块区域都被明确的选择了类型上

于是乎，很容易就可以想到求最小的贡献就是直接最小割了

那么如何建图？

（相同的有额外收益） 则源点向所有点连商业区的收益，所有点向汇点连工业区的收益，相邻的点连双向边额外的收益

答案就是总收益减去最小割

T1就是这样

#include<bits/stdc++.h>

using namespace std;

const int inf=1e9+;

const int maxn=+;

int n,m,tot=-,s,t;

int head[maxn*maxn],c[maxn][maxn],chead[maxn*maxn],vis[maxn*maxn];

int l[]={,},r[]={,};

struct EDGE

{

    int to,next,cap;

}edge[maxn<<];

inline int read()

{

    char ch=getchar();

    int s=,f=;

    while (!(ch>=''&&ch<='')) {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int get(int x,int y)

{

    return (x-)*m+y;

}

void add(int x,int y,int z1,int z2)

{

    edge[++tot]=(EDGE){y,head[x],z1};

    head[x]=tot;

    edge[++tot]=(EDGE){x,head[y],z2};

    head[y]=tot;

}

bool bfs()

{

    memset(vis,,sizeof(vis));

    queue <int> q;

    vis[s]=;

    q.push(s);

    while (!q.empty())

    {

        int k=q.front();q.pop();

        for (int i=head[k];i!=-;i=edge[i].next)

        {

            int y=edge[i].to;

            if (!vis[y]&&edge[i].cap)

            {

                vis[y]=vis[k]+;

                q.push(y);

            }

        }

    }

    return vis[t]!=;

}

int dfs(int x,int flow)

{

    if (x==t||!flow) return flow;

    int f,a=;

    for (int &i=chead[x];i!=-;i=edge[i].next)

    {

        int y=edge[i].to;

        if (vis[y]==vis[x]+&&(f=dfs(y,min(edge[i].cap,flow)))>)

        {

            edge[i].cap-=f;

            edge[i^].cap+=f;

            a+=f;

            flow-=f;

            if (flow==) break;

        }

    }

    if (a==) vis[x]=-;

    return a;

}

int dinic()

{

    int ans=;

    while (bfs())

    {

        for (int i=;i<=n*m+;i++) chead[i]=head[i];

        ans+=dfs(s,inf);

    }

    return ans;

}

int main()

{

    int ans=;

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

    s=;t=n*m+;

    memset(head,-,sizeof(head));

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

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

    {

    int x=read();

    add(s,get(i,j),x,);

    ans+=x;

}

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

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

    {

    int x=read();

    add(get(i,j),t,x,);

    ans+=x;

}

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

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

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

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

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

    for (int k=;k<=;k++)

    {

        int x1=i+l[k],y1=j+r[k];

        if (x1<=||x1>n||y1<=||y1>m) continue;

        add(get(i,j),get(x1,y1),c[i][j]+c[x1][y1],c[i][j]+c[x1][y1]);

        ans+=(c[i][j]+c[x1][y1]);

}

    printf("%d",ans-dinic());

    return ;

}

巴特西

[GDKOI2010] 圈地计划(网络流)

Description

最新文章

热门文章