當前位置:首頁 > 資訊 > info6 > 正文

【2011集訓隊出題】圈地計劃

發表于: 2016-11-17   作者:chen1352   來源:轉載   瀏覽:
摘要: 題目最近房地產商GDOI(GroupofDumbbellsOrIdiots)從NOI(NutsOldIdiots)手中得到了一塊開發土地。據了解,這塊土地是一塊矩形的區域,可以縱橫劃分為N×M塊小區域。GDOI要求將這些區域分為商業區和工業區來開發。根據不同的地形環境,每塊小區域建造商業區和工業區能取得不同的經濟價值。更具體點,對于第i行第j列的區域,建造商業區將得到Aij收益,建造工業區將得到B

題目

  最近房地產商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求出一個收益最大的方案么?

分析

二元關系,最小割。
先把總收益求出來,在減去最小割。
連邊,對于兩個相鄰的點x,y。
源點點S向x連a[x]的邊,向y連b[y]的邊。
x向匯點T連b[x]的邊,y向匯點T連a[y]的邊。
x、y之間連c[x]+c[y]的雙向邊。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=2147483647;
const long long mo=1000000007;
const long long N=10010;
using namespace std;
long long next[N*7],last[N*7],to[N*7],up[N*7],n,m,d[N*10],dis[N],tot;
long long f[N*7],ans,c[111][111];
long long zz[4][2]=
{
 {0,1},
 {1,0},
 {0,-1},
 {-1,0}
};
long long bj(long long x,long long y,long long z)
{
    next[++tot]=last[x];
    last[x]=tot;
    to[tot]=y;
    f[tot]=z;
    next[++tot]=last[y];
    last[y]=tot;
    to[tot]=x;
    f[tot]=0;
}
bool bfs()
{
    memset(dis,0,sizeof(dis));
    d[1]=0;
    dis[0]=1;
    long long head=0,tail=1,k;
    while(head<tail)
    {
        k=d[++head];
        for(long long i=last[k];i;i=next[i])
        {
            long long j=to[i];
            if(f[i]>0 && !dis[j])
            {
                d[++tail]=j;
                dis[j]=dis[k]+1;
            }
        }
    }
    return dis[n*m+m];
}
long long aug(long long x,long long y)
{
    if(x==n*m+m) return y;
    long long cross=0;
    for(long long i=last[x];i;i=next[i])
    {
        long long j=to[i];
        if(dis[x]+1==dis[j] && f[i]>0)
        {
            long long o=aug(j,min(y,f[i]));
            if(o>0)
            {
                y-=o;
                f[i]-=o;
                f[i^1]+=o;
                cross+=o;
            }
        }
    }
    return cross;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    tot=1;
    for(long long i=1;i<=n;i++)
        for(long long j=1;j<=m;j++)
        {
            long long pos=(i-1)*m+j;
            long long x;
            scanf("%lld",&x);
            ans+=x;
            if(i%2 && j%2 || i%2==0 && j%2==0) bj(0,pos,x);
            else bj(pos,n*m+m,x);
        }
    for(long long i=1;i<=n;i++)
        for(long long j=1;j<=m;j++)
        {
            long long pos=(i-1)*m+j;
            long long x;
            scanf("%lld",&x);
            ans+=x;
            if(i%2 && j%2 || i%2==0 && j%2==0) bj(pos,n*m+m,x);
            else bj(0,pos,x);
        }
    for(long long i=1;i<=n;i++)
        for(long long j=1;j<=m;j++)
            scanf("%lld",&c[i][j]);
    for(long long i=1;i<=n;i++)
        for(long long j=1;j<=m;j++)
            for(long long k=0;k<=3;k++)
            {
                long long xx=i+zz[k][0],yy=j+zz[k][1];
                if(xx<1 || yy<1 || xx>n || yy>m) continue;
                long long pos=(i-1)*m+j,pos1=(xx-1)*m+yy;
                bj(pos,pos1,c[i][j]+c[xx][yy]);
                ans+=c[i][j];
            }
    while(bfs())
        ans-=aug(0,maxlongint);
    cout<<ans<<endl;
}

【2011集訓隊出題】圈地計劃

版權所有 IT知識庫 CopyRight ? 2009-2015 IT知識庫 IT610.com , All Rights Reserved. 京ICP備09083238號
广东25选5开奖结果