POJ2446 二分匹配

题意：

给你一个n*m的格子，问你能不能用1*2的格子把他铺满，有的位置是不能被铺的。

思路：

水题，直接把个相邻的并且都是可以铺的点连一条边然后匹配一遍就行了，提醒一个地方，就是输入不能铺的坐标的时候是先输入列再输入行。

#include<stdio.h>

#include<string.h>

#define N_node 1500

#define N_edge 6000

typedef struct

{

   int to ,next;

}STAR;

STAR E[N_edge];

int list[N_node] ,tot;

int mk_dfs[N_node] ,mk_gx[N_node];

int map[40][40];

void add(int a ,int b)

{

   E[++tot].to = b;

   E[tot].next = list[a];

   list[a] = tot;

}

int DFS_XYL(int x)

{

   for(int k = list[x] ;k ;k = E[k].next)

   {

      int to = E[k].to;

      if(mk_dfs[to]) continue;

      mk_dfs[to] = 1;

      if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to]))

      {

         mk_gx[to] = x;

         return 1;

      }

   }

   return 0;

}

int main ()

{

   int n ,m ,k ,i ,j;

   int a ,b;

   while(~scanf("%d %d %d" ,&n ,&m ,&k))

   {

      memset(map ,0 ,sizeof(map));

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

      {

         scanf("%d %d" ,&b ,&a);

         map[a][b] = 1;

      }

      memset(list ,0 ,sizeof(list));

      tot = 1;

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

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

      {

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

         int now = (i - 1) * m + j;

         if(i < n && !map[i+1][j])

         add(now ,now + m);

         if(j < m && !map[i][j+1])

         add(now ,now + 1);

         if(i > 1 && !map[i-1][j])

         add(now ,now - m);

         if(j > 1 && !map[i][j-1])

         add(now ,now - 1);

      }

      int sum = 0;

      memset(mk_gx ,255 ,sizeof(mk_gx));

      for(i = 1 ;i <= n * m ;i ++)

      {

         memset(mk_dfs ,0 ,sizeof(mk_dfs));

         sum += DFS_XYL(i);

      }

      if(sum  == n * m - k)

      puts("YES");

      else

      puts("NO");

   }

   return 0;

}

巴特西

POJ2446 二分匹配

最新文章

热门文章