POJ2226 不错的最小顶点覆盖

题意：

给你一个n * m 的矩阵，上面有" * " 和 " . " ，让你用少的木板吧所有" * "覆盖，木板宽度是1，长度随意，木板可以重叠，但是不能覆盖到" . "上。

思路：

这个题目建图方式不错，回想下最基本的最小定点覆盖，也是在n * m 的矩阵上，覆盖某些点，但是可以覆盖" . "那样直接匹配行列就行了，这个如果是***.***就得用两个了，那我们可以直接把所有的行都离散化出来，吧所有的列都离散化出来，比如

*.*. 按照行离散成 1.2. 按照列离散成 1 . 4 .

.*** .333 . 3 4 5

***. 444. 2 3 4 .

..*. ..5. . . 4 .

接下来就直接正常行列匹配就行了（"*"所在的行和列匹配）。

#include<stdio.h>

#include<string.h>

#define N_node 3000

#define N_edge 6000

typedef struct

{

   int to ,next;

}STAR;

typedef struct

{

   int r ,l;

}NODE;

STAR E[N_edge];

NODE map[60][60];

int mk_dfs[N_node] ,mk_gx[N_node];

int list[N_node] ,tot;

int mp[60][60];

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 ,i ,j ,maxr;

   char str[60];

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

   {

      memset(mp ,0 ,sizeof(mp));

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

      {

         scanf("%s" ,str);

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

         mp[i][j] = str[j-1] == '*';

      }

      int now = 0;

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

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

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

      {

         if(!mp[i][j])

         {

            map[i][j].r = 0;

            continue;

         }

         if(mp[i][j] && !mp[i][j-1])

         map[i][j].r = ++now;

         else map[i][j].r = map[i][j-1].r;

      }

      maxr = now;

      now = 0;

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

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

      {

         if(!mp[i][j])

         {

            map[i][j].l = 0;

            continue;

         }

         if(mp[i][j] && !mp[i-1][j])

         map[i][j].l = ++now;

         else map[i][j].l = map[i-1][j].l;

      }

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

      tot = 1;

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

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

      if(map[i][j].r && map[i][j].l)

      add(map[i][j].r ,map[i][j].l);

      int sum = 0;

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

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

      {

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

         sum += DFS_XYL(i);

      }

      printf("%d\n" ,sum);

   }

   return 0;

}

巴特西

POJ2226 不错的最小顶点覆盖

最新文章

热门文章