「CODEVS1022」覆盖

2014年1月26日4,4280

题目描述 Description

有一个N×M的单位方格中，其中有些方格是水塘，其他方格是陆地。如果要用1×2的矩阵区覆盖（覆盖过程不容许有任何部分重叠）这个陆地，那么最多可以覆盖多少陆地面积。

输入描述 Input Description

输入文件的第一行是两个整数N，M (1<=N，M<=100)，第二行为一个整数K( K<=50)，接下来的K行，每行两个整数X，Y表示K个水塘的行列位置。(1<=X<=N，1<=Y<=M)。

输出描述 Output Description

输出所覆盖的最大面积块（1×2面积算一块）。

样例输入 Sample Input

4 4

6

1 1

1 4

2 2

4 1

4 2

4 4

样例输出 Sample Output

4

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x7fffffff
using namespace std;
int n,m,k,b,w,ans=0;
bool del[101][101];
int head[10001],mark[101][101],h[10001];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
int ne=1;
struct data{int next,to,v;}e[100001];
void insert(int u,int v,int w){
    ne++;e[ne].to=v;
    e[ne].v=w;
    e[ne].next=head[u];
    head[u]=ne;
    ne++;e[ne].to=u;
    e[ne].next=head[v];
    head[v]=ne;
    }
bool jud(int x,int y){if(x<1||y<1||x>n||y>m||del[x][y])return 0;return 1;}
void INS(){
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           if((i+j)%2==0&&!del[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]],1);}
                   }
            }
     }
bool bfs()
{
     int q[10001],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*m+1]==-1)return 0;
     return 1;
     }
int dfs(int x,int f)
{
    if(x==n*m+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%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)
    {
            int x,y;
            scanf("%d%d",&x,&y);
            del[x][y]=1;
            }
    b=0,w=(n*m+1)/2;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
               if((i+j)%2==0){b++;mark[i][j]=b;}
               else{w++;mark[i][j]=w;}
    for(int i=1;i<=b;i++)insert(0,i,1);
    for(int i=b+1;i<=n*m;i++)insert(i,n*m+1,1);
    INS();
    dinic();
    printf("%d",ans);
    return 0;
    }

#include<iostream>

#include<cstdio>

#include<cstring>

#define INF 0x7fffffff

using namespace std;

int n,m,k,b,w,ans=0;

bool del[101][101];

int head[10001],mark[101][101],h[10001];

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

int ne=1;

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

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

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

e[ne].v=w;

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

head[u]=ne;

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

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

head[v]=ne;

}

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

void INS(){

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

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

if((i+j)%2==0&&!del[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]],1);}

}

bool bfs()

{

int q[10001],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*m+1]==-1)return 0;

return 1;

}

int dfs(int x,int f)

{

if(x==n*m+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%d%d",&n,&m,&k);

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

{

int x,y;

scanf("%d%d",&x,&y);

del[x][y]=1;

}

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

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

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

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

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

for(int i=1;i<=b;i++)insert(0,i,1);

for(int i=b+1;i<=n*m;i++)insert(i,n*m+1,1);

INS();

dinic();

printf("%d",ans);

return 0;

}

« NOI2006最大获利「JoyOI1338」QQ农场 »

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

「CODEVS1022」覆盖

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

代码

分类目录

热门文章

Myfriends

近期评论