「JoyOI1338」QQ农场

2014年1月28日3,0650

背景 Background

Sandytea前段时间沉迷于QQ农场中……一天夜里，他梦见来到好友X的农场上……

描述 Description

这个农场和游戏中略有不同。土地实际上是一个边长为N的正方形，由N*N块土地组成。
在每块土地上，都种有一种农作物。如果他选择摘取一块土地上的农作物，就能获得一个固定的利润(当然，这个利润是正数)。不同土地上的利润多半是不同的。
贪心的Sandytea本想摘取所有土地上的农作物。但是正当他准备行动时，却被告知不允许摘取了两块有公共边的土地上的作物，否则就会被主人的狗发现。
Sandytea想知道，在不被狗抓住的前提下，他能获得的最大利益是多少。

输入格式 InputFormat

第一行：一个整数N，表示土地是一个边长为N的正方形。
下面N行：每行N个正整数，描述了各块土地上的农作物的单位价值。

输出格式 OutputFormat

输出一行，包含一个整数，为最大的收益。

样例输入 SampleInput

2
7 7
54 54

样例输出 SampleOutput

数据范围和注释 Hint

数据范围：
有10分的数据满足：N≤6
另有20分的数据满足：N≤13
另有30分的数据满足：N≤50
另有40分的数据满足：N≤200
所有数据满足：每块土地上作物的价值不超过100。

代码。。

蒟蒻只会dinic

#include<iostream>
#include<cstring>
#include<cstdio>
#define INF 0x7fffffff
using namespace std;
int n,cnt=1,head[40002],h[40002],ans;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int mp[201][201],mark[201][201];
struct data{int to,next,v;}e[1000001];
bool jud(int x,int y){if(x<1||y<1||x>n||y>n)return 0;return 1;}
void insert(int u,int v,int w){
    cnt++;e[cnt].to=v;
    e[cnt].v=w;
    e[cnt].next=head[u];
    head[u]=cnt;
    cnt++;e[cnt].to=u;
    e[cnt].next=head[v];
    head[v]=cnt;
    }
void INS(){
     for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
           if((i+j)%2==0)
           {
              insert(0,mark[i][j],mp[i][j]);
              for(int k=0;k<4;k++)
              {
                  if(jud(i+xx[k],j+yy[k])){insert(mark[i][j],mark[i+xx[k]][j+yy[k]],INF);}
                   }
            }
           else insert(mark[i][j],n*n+1,mp[i][j]);
     }
bool bfs()
{
     int q[40002],t=0,w=1,i,now;
     memset(h,-1,sizeof(h));
     q[0]=h[0]=0;
     while(t<w)
     {
            now=q[t];t++;
            i=head[now];
            while(i)
            {
                  if(e[i].v&&h[e[i].to]<0){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}
                  i=e[i].next;
             }
     }
     if(h[n*n+1]==-1)return 0;
     return 1;
     }
int dfs(int x,int f)
{
    if(x==n*n+1)return f;
    int i=head[x];
    int w,used=0;
    while(i)
    {
            if(e[i].v&&h[e[i].to]==h[x]+1)
            {
                w=f-used;
                w=dfs(e[i].to,min(w,e[i].v));   
                e[i].v-=w;
                e[i^1].v+=w;
                used+=w;
                if(used==f)return f;                      
                }
                i=e[i].next;
            }
    if(!used)h[x]=-1;
    return used;
    }
void dinic(){while(bfs())ans-=dfs(0,INF);}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
       {
          scanf("%d",&mp[i][j]);
          ans+=mp[i][j];
          }
    int b=0,w=(n*n+1)/2; 
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           if((i+j)%2==0){b++;mark[i][j]=b;}
               else{w++;mark[i][j]=w;}
    INS();
    dinic();
    printf("%d",ans);
    return 0;
    }

#include<iostream>

#include<cstring>

#include<cstdio>

#define INF 0x7fffffff

using namespace std;

int n,cnt=1,head[40002],h[40002],ans;

int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};

int mp[201][201],mark[201][201];

struct data{int to,next,v;}e[1000001];

bool jud(int x,int y){if(x<1||y<1||x>n||y>n)return 0;return 1;}

void insert(int u,int v,int w){

cnt++;e[cnt].to=v;

e[cnt].v=w;

e[cnt].next=head[u];

head[u]=cnt;

cnt++;e[cnt].to=u;

e[cnt].next=head[v];

head[v]=cnt;

}

void INS(){

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

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

if((i+j)%2==0)

{

insert(0,mark[i][j],mp[i][j]);

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

{

if(jud(i+xx[k],j+yy[k])){insert(mark[i][j],mark[i+xx[k]][j+yy[k]],INF);}

}

else insert(mark[i][j],n*n+1,mp[i][j]);

}

bool bfs()

{

int q[40002],t=0,w=1,i,now;

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

q[0]=h[0]=0;

while(t<w)

{

now=q[t];t++;

i=head[now];

while(i)

{

if(e[i].v&&h[e[i].to]<0){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}

i=e[i].next;

}

if(h[n*n+1]==-1)return 0;

return 1;

}

int dfs(int x,int f)

{

if(x==n*n+1)return f;

int i=head[x];

int w,used=0;

while(i)

{

if(e[i].v&&h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(w,e[i].v));

e[i].v-=w;

e[i^1].v+=w;

used+=w;

if(used==f)return f;

}

i=e[i].next;

}

if(!used)h[x]=-1;

return used;

}

void dinic(){while(bfs())ans-=dfs(0,INF);}

int main()

{

scanf("%d",&n);

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

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

{

scanf("%d",&mp[i][j]);

ans+=mp[i][j];

}

int b=0,w=(n*n+1)/2;

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

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

if((i+j)%2==0){b++;mark[i][j]=b;}

else{w++;mark[i][j]=w;}

INS();

dinic();

printf("%d",ans);

return 0;

}

« 「CODEVS1022」覆盖「CODEVS1922」骑士共存问题 »

hzwer.com _ Home | http://hzwer.com

「JoyOI1338」QQ农场

分类目录

热门文章

Myfriends

近期评论