poj 2226 Muddy Fields（最小点集覆盖）

证明最大匹配=最小点集覆盖http://blog.csdn.net/wmn_wmn/article/details/7275648

Sample Input

4 4
*.*.
.***
***.
..*.

Sample Output

4

题意：有一块地，由于下雨，使部分面积出现泥泞，但牛只吃干净的草，现在想把出现泥泞的地方用木板铺盖上，
这样牛的蹄子就不会因为踩到泥泞的地方弄脏草地上的草；一个n行m列的矩阵，"*“代表泥泞的土地，”.“代表草地,
求最少覆盖的木板个数。注意：木板宽始终为1，长不限制；
求最小覆盖=最大匹配；
解析：这里我用0表示草地，则按行来铺木板，最有个数是5
1 0 2 0 
0 3 3 3
4 4 4 0
0 0 5 0
按列来铺木板
1 0 4 0
0 3 4 5
2 3 4 0
0 3 4 0
这样存储之后分成两个集合进行做大匹配筛选，就得到最小覆盖木板数

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 int map[1500][1500],a[1500],b[1500];
  4 int k,p;
  5 struct PP
  6 {
  7     int id;
  8     int x,y;
  9 }s1[1500],s2[1500];
 10 int met(int x)//找出最优匹配值
 11 {
 12     int i;
 13     for(i=0;i<p;i++)
 14     {
 15         if(b[i]==0&&map[x][i])
 16         {
 17             b[i]=1;
 18             if(a[i]==-1||met(a[i]))
 19             {
 20                 a[i]=x;
 21                 return 1;
 22             }
 23         }
 24     }
 25     return 0;
 26 }
 27 int main()
 28 {
 29     int n,m,i,j;
 30     char str[1500][1500];
 31     while(scanf("%d%d",&n,&m)!=-1)
 32     {
 33         k=0;
 34         for(i=0;i<n;i++)//按行找出每行的最有覆盖面积
 35         {
 36             scanf("%s",str[i]);
 37             j=0;
 38             s1[k].id=i;//用来存储每行的覆盖数
 39             s1[k].x=-1;//将第i行所在的列初始化
 40             s1[k].y=-1;//s1[k].x与s[k].y是用来标记第i行中被覆盖木板的起始列
 41             while(j<m)
 42             {
 43                 if(str[i][j]=='*')
 44                 {
 45                     if(s1[k].x==-1)
 46                     {
 47                         s1[k].x=j;
 48                         s1[k].y=j;
 49                     }
 50                     else
 51                         s1[k].y++;
 52                     if(str[i][j+1]=='.'||j+1==m)
 53                     {
 54                         k++;
 55                         s1[k].id=i;
 56                         s1[k].x=-1;
 57                         s1[k].y=-1;
 58                     }
 59                 }
 60                 j++;
 61             }
 62         
 63         }
 64             p=0;
 65             for(j=0;j<m;j++)//同理，用s2[k]存储每列的木板覆盖数；
 66             {
 67                 i=0;
 68                 s2[p].id=j;
 69                 s2[p].x=-1;
 70                 s2[p].y=-1;
 71                 while(i<n)
 72                 {
 73                     if(str[i][j]=='*')
 74                     {
 75                         if(s2[p].x==-1)
 76                         {
 77                             s2[p].x=i;
 78                             s2[p].y=i;
 79                         }
 80                         else
 81                             s2[p].y++;
 82                         if(str[i+1][j]=='.'||i+1==n)
 83                         {
 84                             p++;
 85                             s2[p].id=j;
 86                             s2[p].x=-1;
 87                             s2[p].y=-1;
 88                         }
 89                     }
 90                     i++;
 91                 }
 92                 
 93             }
 94             memset(map,0,sizeof(map));
 95             for(i=0;i<k;i++)
 96             {
 97                 for(j=0;j<p;j++)
 98                 {
 99                     if(s2[j].x<=s1[i].id&&s1[i].id<=s2[j].y&&s1[i].x<=s2[j].id&&s2[j].id<=s1[i].y)
100                         map[i][j]=1;
101                 }
102             }
103             int num=0;
104             memset(a,-1,sizeof(a));
105             for(i=0;i<k;i++)
106             {
107                 memset(b,0,sizeof(b));
108                 num+=met(i);
109             }
110             printf("%d\n",num);
111     }
112     return 0;
113 }