【poj2226】 Muddy Fields

题意

　　给出一个只包含‘．’和‘＊’的矩阵，用任意长度的宽为1的木板覆盖所有的‘＊’而不覆盖‘．’，木板必须跟矩形的长或宽平行。问最少需要多少块木板。

Solution

　　这道题的构图非常巧妙，堪称经典构图。对于每一个‘＊’，要么就是被横的木板覆盖，要么就是被竖的木板覆盖，而木板的长度一定都是取到最长（因为题目没有说木板不能重叠，所以木板尽可能长不会使答案变大）。

　　假设我们全部用横木板进行覆盖，那么可以很简单的统计出哪些地方用第几块木板覆盖；同样如果我们全部用竖的木板进行覆盖，也可以统计出哪些地方用第几块木板覆盖。所以我们最后要选择的木板就在这些木板中产生。
　　
　　拿样例来举个例子：
　　　　　　　　　　　　　　　横：1 0 2 0　　　竖：1 0 4 0
　　　　　　　　　　　　　　　　　0 3 3 3　　　　　0 3 4 5
　　　　　　　　　　　　　　　　　4 4 4 0　　　　　2 3 4 0
　　　　　　　　　　　　　　　　　0 0 5 0　　　　　0 0 4 0
　　
　　所以现在问题就转化成了如何选取最少的木板，使所有的‘＊’都被覆盖。这是不是很像二分图匹配中的最小点覆盖，可问题是我们怎么对它构图呢？

　　对于每一个‘＊’，都会有一个横木板和竖木板在这个位置相交。那么如果我们对于每一个‘＊’给在这里相交的横木板和竖木板的编号连一条边，是不是每一条边都表示一个‘＊’呢？答案是显然的。问题到这里也就迎刃而解了。最小点覆盖＝最大匹配数，所以我们只需要连完边后跑匈牙利就可以了。

代码

// poj2226

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<string>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    int f,x=0;char ch=getchar();

    while (ch<='0' || ch>'9') {if (ch=='-') f=-1;else f=1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=1000;

struct edge {int to,next;}e[maxn*maxn];

int n,m,cnt,head[maxn],a[maxn][maxn],x[maxn][maxn],y[maxn][maxn],p[maxn],vis[maxn];

char s[maxn];

void insert(int u,int v) {

    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;

}

bool find(int x) {

    for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to]) {

            vis[e[i].to]=1;

            if (p[e[i].to]==0 || find(p[e[i].to])) {

                p[e[i].to]=x;

                return 1;

            }

        }

    return 0;

}

int main() {

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

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

        scanf("%s",s);

        for (int j=0;j<m;j++) {

            if (s[j]=='*') a[i][j+1]=1;

            else a[i][j+1]=0;

        }

    }

    int xx=0,yy=0;

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

        for (int j=1;j<=m;j++) if (a[i][j]>0) {

                x[i][j]=++xx;

                while (j<m && a[i][j+1]>0) {j++;x[i][j]=xx;}

            }

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

        for (int i=1;i<=n;i++) if (a[i][j]>0) {

                y[i][j]=++yy;

                while (i<n && a[i+1][j]>0) {i++;y[i][j]=yy;}

            }

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

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

            if (a[i][j]>0) insert(x[i][j],y[i][j]);

    int ans=0;

    for (int i=1;i<=xx;i++) {

        for (int j=1;j<=yy;j++) vis[j]=0;

        if (find(i)) ans++;

    }

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

    return 0;

}

巴特西

【poj2226】 Muddy Fields

题意

Solution

代码

最新文章

热门文章