「CODEVS1922」骑士共存问题

2014年2月2日4,8690

题目描述 Description

在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍，骑士不得进入。

对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
士，使得它们彼此互不攻击。

输入描述 Input Description

第一行有2 个正整数n 和m (1<=n<=200, 0<=m<n^2)，
分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
碍的方格坐标。

输出描述 Output Description

将计算出的共存骑士数输出

样例输入 Sample Input

3 2

1 1

3 3

样例输出 Sample Output

5

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 0x7fffffff
using namespace std;
int n,m,bl,wt,ans,cnt=1;
bool del[201][201];
int mark[201][201];
int xx[8]={1,1,2,2,-1,-1,-2,-2},
    yy[8]={2,-2,1,-1,2,-2,1,-1};
struct data{int to,next,v;}e[500001];
int head[40002],h[40002];
void insert(int u,int v,int w)
{
     cnt++;
     e[cnt].to=v;
     e[cnt].next=head[u];
     head[u]=cnt;
     e[cnt].v=w;
     cnt++;
     e[cnt].to=u;
     e[cnt].next=head[v];
     head[v]=cnt;
 }
void build()
{
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
             if(del[i][j])continue;
             else if(mark[i][j]<bl)
             {
             for(int k=0;k<8;k++)
             {
                     int nowx=i+xx[k],nowy=j+yy[k];
                     if(nowx<1||nowy<1||nowx>n||nowy>n||del[nowx][nowy])continue;
                     insert(mark[i][j],mark[nowx][nowy],INF);
                     }
             insert(0,mark[i][j],1);
             }
             else insert(mark[i][j],wt,1);
 }
bool bfs()
{
     int q[40002],t=0,w=1,i,now;
     memset(h,-1,sizeof(h));
     h[0]=q[0]=0;
     while(t<w)
     {
               now=q[t];t++;
               i=head[now];
               while(i)
               {
                       if(h[e[i].to]==-1&&e[i].v){h[e[i].to]=h[now]+1;q[w++]=e[i].to;}
                       i=e[i].next;
                       }
               }
     if(h[wt]==-1)return 0;
     return 1;
 }
int dfs(int x,int f)
{
    if(x==wt)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",&n,&m);
    for(int i=1;i<=m;i++)
    {
            int x,y;
            scanf("%d%d",&x,&y);
            del[x][y]=1;
            }
    bl=1,wt=(n*n+1)/2+1;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
          if((i+j)%2==0){mark[i][j]=bl;bl++;}
          else {mark[i][j]=wt;wt++;}
    build();
    dinic();
    printf("%d",n*n-m-ans);
    return 0;
}

100

#include<iostream>

#include<cstdio>

#include<cstring>

#define INF 0x7fffffff

using namespace std;

int n,m,bl,wt,ans,cnt=1;

bool del[201][201];

int mark[201][201];

int xx[8]={1,1,2,2,-1,-1,-2,-2},

yy[8]={2,-2,1,-1,2,-2,1,-1};

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

int head[40002],h[40002];

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

{

cnt++;

e[cnt].to=v;

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

head[u]=cnt;

e[cnt].v=w;

cnt++;

e[cnt].to=u;

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

head[v]=cnt;

}

void build()

{

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

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

if(del[i][j])continue;

else if(mark[i][j]<bl)

{

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

{

int nowx=i+xx[k],nowy=j+yy[k];

if(nowx<1||nowy<1||nowx>n||nowy>n||del[nowx][nowy])continue;

insert(mark[i][j],mark[nowx][nowy],INF);

}

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

}

else insert(mark[i][j],wt,1);

}

bool bfs()

{

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

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

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

while(t<w)

{

now=q[t];t++;

i=head[now];

while(i)

{

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

i=e[i].next;

}

if(h[wt]==-1)return 0;

return 1;

}

int dfs(int x,int f)

{

if(x==wt)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",&n,&m);

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

{

int x,y;

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

del[x][y]=1;

}

bl=1,wt=(n*n+1)/2+1;

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

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

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

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

build();

dinic();

printf("%d",n*n-m-ans);

return 0;

}

« 「JoyOI1338」QQ农场无聊写的A+B问题。。。 »

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

「CODEVS1922」骑士共存问题

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

代码

分类目录

热门文章

Myfriends

近期评论