[Usaco2005 Jan]Muddy Fields泥泞的牧场

Description

雨连续不断的击打了放牛的牧场，一个R行C列的格子(1<=R<=50,1<=C<=50)。虽然这对草来说是件好事，但这却使得一些没有草遮盖的土地变得很泥泞。牛们是很小心的食草动物；他们不想在吃草时把蹄子弄脏。为了避免它们把蹄子弄脏，农夫约翰要在那些泥泞的地方铺上木板子。每个1个单位宽，长度任意。每个板子都必须放到与牧场一边平行。农夫约翰希望用最少的板子来覆盖泥泞的部分。一些地方可能需要多于一块板子来覆盖。木板不可以遮住草地，剥夺牛吃草的地方，但是他们可以相互重叠。计算最少需要多少块板子来覆盖所有的泥地。

Input

第一行：两个整数R和C，由空格隔开。
第2到第R+1行：每行为一个长度为C的字符串。'*'代表泥地，'.'代表草地。

无空格。

Output

第一行：一个整数，其值为最少需要的板子数目

Sample Input

4 4

*.*.

.***

***.

..*.

Sample Output

4

OUTPUT DETAILS:

板子 1, 2, 3 和 4 是这样摆放的:

1.2.

.333

444.

..4.

板子2与3，4重叠。

二分图匹配，泥泞点要么被横向的板子覆盖，要么被纵向的板子覆盖，但是板子不能盖在草地上。所以我们找下联通块，再做二分图最大匹配。

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read(){

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

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x>=10)     print(x/10);

	putchar(x%10+'0');

}

const int N=5e1;

int path[(N*N>>1)+10],pre[N*N+10],now[(N*N>>1)+10],child[N*N+10];

int A[N+10][N+10],B[N+10][N+10];

int tot,n,m,Acnt,Bcnt,ans;

bool use[(N*N>>1)+10];

char map[N+10][N+10];

void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}

bool check(int x){

    for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){

        if (use[son])   continue;

        use[son]=1;

        if (path[son]<0||check(path[son])){path[son]=x;return 1;}

    }

    return 0;

}

int main(){

    n=read(),m=read();

    for (int i=1;i<=n;i++)   scanf("%s",map[i]+1);

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

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

            if (map[i][j]=='*'){

                A[i][j]=j>1&&map[i][j-1]=='*'?A[i][j-1]:++Acnt;

                B[i][j]=i>1&&map[i-1][j]=='*'?B[i-1][j]:++Bcnt;

            }

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

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

            if (map[i][j]=='*')

                join(A[i][j],B[i][j]);

    memset(path,-1,sizeof(path));

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

        memset(use,0,sizeof(use));

        if (check(i))   ans++;

    }

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

    return 0;

}

巴特西

[Usaco2005 Jan]Muddy Fields泥泞的牧场

最新文章

热门文章