P1035

P1035

时间限制: 1 Sec  内存限制: 128 MB
提交: 87  解决: 36
[提交][状态][讨论版]

题目描述

给出一张n*n(n< =100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。

输入

第一行为n，m（表示有m个删除的格子） 第二行到m+1行为x,y，分别表示删除格子所在的位置 x为第x行 y为第y列

输出

一个数，即最大覆盖格数

样例输入

8 0

样例输出

32

提示

经典问题

建图，比较简单，一般人都想得到，所以一个点与其上下左右的点连边，然后就可以了，求一次二分图最大匹配。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int x[]={,,,-},y[]={-,,,};

 int n,m;

 bool map[][],flag[];

 int head[],cnt,next[],rea[];

 int fa[];

 void add(int u,int v)

 {

     cnt++;

     next[cnt]=head[u];

     head[u]=cnt;

     rea[cnt]=v;

 }

 bool dfs(int u)

 {

     for(int i=head[u];i!=-;i=next[i])

     {

         int v=rea[i];

         if(flag[v]==false)

         {

             flag[v]=;

             if(fa[v]==-||dfs(fa[v]))

             {

                 fa[v]=u;

                 return true;

             }

         }

     }

     return false;

 }

 int solve()

 {

     int num=;

     memset(fa,-,sizeof(fa));

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

     {

         memset(flag,false,sizeof(flag));

         num+=dfs(i);

     }

     return num;

 }

 int main()

 {

     cnt=;

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

     memset(map,false,sizeof(map));

     scanf("%d%d",&n,&m);

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

     {

         int x,y;

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

         map[x][y]=true;

     }

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

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

           if(!map[i][j])

           {

               int numx=(i-)*n+j;

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

               {

                   int xx=i+x[k],yy=j+y[k];

                   if(xx>=&&xx<=n&&yy>=&&yy<=n&&!map[xx][yy])

                    {

                       int numy=(xx-)*n+yy;

                       add(numx,numy);

                    }

               }

            }

     printf("%d\n",solve()/);

 }