POJ 2226 Muddy Fields(最小覆盖数)

POJ 2226 Muddy Fields(最小覆盖数)

http://poj.org/problem?id=2226

题意:

农夫John的养牛场，是一个R 行C 列的矩形，一场大雨后，养牛场低洼的地方都有了积水。John 的牛都很娇贵的，他们吃草的时候，不想把他们的蹄子给弄脏了。为了不让牛儿们把它们的蹄子弄脏，John 决定把有水的地方铺上木板。他的木板是宽度为1，长度没有限制的。

他想用最少数目的木板把所有有水的低洼处给覆盖上，前提是木板不能覆盖草地，但是可以重叠。

分析:

先来看看前人的思路:

这道题，构图确实比较巧妙，如果有连续的低洼处，假设是横排的，那么这几个连续的低洼处可以拿一个板子来覆盖，同样，如果竖排也有连续的低洼处，那么也可以拿一个板子来覆盖。这样，当一个低洼处既可以拿横着的板子，也可以拿竖着的板子覆盖时，就是相交了。那么这个交线就代表了一个低洼处，它既可以被横着盖，也可以被竖着盖。现在我们把所有横排的低洼处作为left（连续的低洼处作为1个板），竖着的也同理，以例题如下表式：

Sample:

4 4

*.*.

.***

***.

..*.

把行里面连在一起的坑连起来视为一个点，即一块横木板，编上序号，Sample则转化为：

1 0 2 0

0 3 3 3

4 4 4 0

0 0 5 0

把这些序号加入X集合，再按列做一次则为：

1 0 4 0

0 3 4 5

2 3 4 0

0 0 4 0

同样加入Y集合.

一个坑只能被横着的或者被竖着的木板盖住，将原图的坑的也标上不同的序号，一共九个坑

1 . 2 .

. 3 4 5

6 7 8 .

. . 9 .

图中的2号低洼处既可以拿横着的2号板，也可以拿竖着的4号板来覆盖，那么横2号版和竖4号板之间就有一条边，边实际表示了低洼处，例如2号低洼处的边为{2,4}，可以理解为2号低洼处可以由横2号板或竖4号板覆盖。用最少的点把所有的边连起来，这样就是最小点覆盖。

我的补充:

首先对于图中的每个坑(网格),它可以只可以用横木板或竖木板覆盖(或者两者重叠都用了).

第二, 由于木板长度任意,所以我们选木板的时候,木板在不覆盖草地的前提下,应该越长越好.(选用长木板所需的木板数一定不会比 选用短木板所需的木板数多 且任意木板是允许重叠的)

当我们全用横木板且木板长度劲量长时,得到的覆盖结果如之前的2图. 当我们全用竖木板且木板长度劲量长时,得到的覆盖结果如之前的3图. 现在我们的问题是 如果从2图中和3图中选出最少总数的(位置已经确定)木板,使得这些木板构成的新图中,正好所有水坑都被盖住了?

把2图中的横木板看成左边的点集,把3图中的竖木板看成右边的点集,对于一个坑,如果它能用横i或竖j木板覆盖,那么从左i点到右j点有一条无向边. 现在的问题是 我们最少需要选择多少个(左边或右边的)点能使得新图所有的边都被覆盖? 即新图的最小覆盖集(=最大匹配数)

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn= 1000+5;

struct Max_Match
{
    int n,m;
    bool g[maxn][maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n,int m)
    {
        this->n=n;
        this->m=m;
        memset(g,0,sizeof(g));
        memset(left,-1,sizeof(left));
    }

    bool match(int u)
    {
        for(int v=1;v<=m;v++)if(g[u][v] && !vis[v])
        {
            vis[v]=true;
            if(left[v]==-1 || match(left[v]))
            {
                left[v]=u;
                return true;
            }
        }
        return false;
    }

    int solve()
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ans++;
        }
        return ans;
    }

}MM;

char map[60][60];
int h[60][60];//横编号
int v[60][60];//竖编号

int main()
{
    int R,C,n,m;
    while(scanf("%d%d",&R,&C)==2)
    {
        memset(map,0,sizeof(map));
        memset(h,0,sizeof(h));
        memset(v,0,sizeof(v));
        for(int i=1;i<=R;i++)
            for(int j=1;j<=C;j++)
                scanf(" %c",&map[i][j]);
        n=m=0;
        for(int i=1;i<=R;i++)//横编号
        for(int j=1;j<=C;j++)if(map[i][j]=='*')
        {
            if(map[i][j-1]=='*') h[i][j]=n;
            else h[i][j]=++n;
        }
        for(int j=1;j<=C;j++)//竖编号
        for(int i=1;i<=R;i++)if(map[i][j]=='*')
        {
            if(map[i-1][j]=='*') v[i][j]=m;
            else v[i][j]=++m;
        }

        MM.init(n,m);
        for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)if(map[i][j]=='*')
        {
            MM.g[h[i][j]][v[i][j]]=true;
        }
        printf("%d\n",MM.solve());
    }
    return 0;
}