Muddy Fields（二分图最大匹配 + 匈牙利算法）

 

Muddy Fields

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7569		Accepted: 2794

Description

Rain has pummeled the cows' field, a rectangular grid of R rows and C columns (1 <= R <= 50, 1 <= C <= 50). While good for the grass, the rain makes some patches of bare earth quite muddy. The cows, being meticulous grazers, don't want to get their hooves dirty while they eat. 

To prevent those muddy hooves, Farmer John will place a number of wooden boards over the muddy parts of the cows' field. Each of the boards is 1 unit wide, and can be any length long. Each board must be aligned parallel to one of the sides of the field. 

Farmer John wishes to minimize the number of boards needed to cover the muddy spots, some of which might require more than one board to cover. The boards may not cover any grass and deprive the cows of grazing area but they can overlap each other. 

Compute the minimum number of boards FJ requires to cover all the mud in the field.

Input

* Line 1: Two space-separated integers: R and C 

* Lines 2..R+1: Each line contains a string of C characters, with '*' representing a muddy patch, and '.' representing a grassy patch. No spaces are present.

Output

* Line 1: A single integer representing the number of boards FJ needs.

Sample Input

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

Sample Output

4

Hint

OUTPUT DETAILS: 

Boards 1, 2, 3 and 4 are placed as follows: 
1.2. 
.333 
444. 
..2. 
Board 2 overlaps boards 3 and 4.

 

       题意：

       给出 N（1 ~ 50） 和 M （1 ~ 50），代表有 N 行 M 列， 每个点状态要不是 “ . ”，要不就是“ * ”，需要用木板覆盖所有的 * ，每块木板长短不限，打横或者打竖放，木板与木板间可以相交搭建。输出最少需要的木板数。

 

        思路：

        二分图最大匹配 + 匈牙利算法。求最小顶点覆盖（用最小的点去覆盖所有的边）。这题与之前做的有道题很类似，横纵坐标建图，但是那个是可以一次性覆盖不连续的点的，而这题是必须一次性要覆盖连续的点。所以对连通块编号，分为横连通块和竖连通块每个点都可以由一个横连通块和纵连通块组成，由此可以建成一个图，找出最少的连通块来覆盖所有的点，故所有的点都化成了线，要覆盖所有的边则是最小顶点覆盖，求出最大匹配即可。思路很重要，感觉这题比较难想。

 

       AC：

#include <cstdio>
#include <string.h>
using namespace std;

typedef struct {
    int x,y;
}node;
node no[55][55];
char s[55][55];
int w[1500][1500],linker[1500],vis[1500];
int n,m,un,vn;

bool dfs(int u) {
    for(int v = 1;v <= vn;v++)
        if(w[u][v] && !vis[v]) {
            vis[v] = 1;
            if(linker[v] == -1 || dfs(linker[v])) {
                linker[v] = u;
                return true;
            }
        }

    return false;
}

int hungary() {
    int res = 0;
    memset(linker,-1,sizeof(linker));
    for(int u = 1;u <= un;u++) {
        memset(vis,0,sizeof(vis));
        if(dfs(u)) res++;
    }
    return res;
}

void build() {
    un = 0;  //行连通块结点
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j) {
            if(s[i][j] == '*') {
                if(j == 1) no[i][j].x = ++un;
                if(j > 1) {
                    if(s[i][j - 1] == '*') no[i][j].x = un;
                    else    no[i][j].x = ++un;
                }
            }
        }

    vn = 0;  //列连通块结点
    for(int j = 1;j <= m;++j)
        for(int i = 1;i <= n;++i) {
            if(s[i][j] == '*') {
                if(i == 1) no[i][j].y = ++vn;
                if(i > 1) {
                    if(s[i - 1][j] == '*') no[i][j].y = vn;
                    else    no[i][j].y = ++vn;
                }
            }
        }

    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
            if(s[i][j] == '*')
               w[no[i][j].x][no[i][j].y] = 1;
}

int main() {
    //freopen("test.in","r",stdin);
    memset(w,0,sizeof(w));
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
            scanf(" %c",&s[i][j]);

    build();

    printf("%d\n",hungary());
    return 0;
}