POJ 2226 Muddy Fields（算法竞赛进阶指南，二分图最小点覆盖）

算法竞赛进阶指南，434页，二分图最小点覆盖
题目意思：
在 n * m 的网格，有些格子泥泞，有些干净的，现在用宽度为1， 长度随意的木板覆盖泥泞点，但不能覆盖
任何的干净点。木板可以重叠，问最少需要多少块木板。
本题要点：
1、首先木板覆盖的只能是单个的泥泞点， 或者是连续的若干个泥泞点。木板不能覆盖 干净点。
依次扫描每一行，碰到连续的若干个泥泞点，就用一块木板覆盖该点。每一块木板编上编号，从1 开始， 这些编号叫做 行泥泞块。
同理，依次扫描每一列，得到 列泥泞块。
以 行泥泞块 块为左部节点， 列泥泞块 为右部节点。 对于每一个 泥泞点，将其所属的 行泥泞块 和 列泥泞块 连边。
因此，构成了 二分图。

2、题目要求用最少的木板，覆盖所有的泥泞点，也就是二分图的最小点覆盖问题。
根据 konig 定理：二分图的最小店覆盖点数，等于二分图的最大匹配包含的边数。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 60;
int n, m;
char field[MaxN][MaxN];
int x[MaxN][MaxN], y[MaxN][MaxN];
const int Len = 1260;
int a[Len][Len], match[Len];
bool vis[Len];
int x_cnt, y_cnt;void init()
{
    //处理行int tot = 1;for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
    if(field[i][j] == '*'){
    x[i][j] = tot;	if(j + 1 == m){
    ++tot;}}else if(field[i][j] == '.'){
    if(j - 1 >= 0 && field[i][j - 1] == '*')++tot;	}}}x_cnt = tot;//处理列tot = 1;for(int j = 0; j < m; ++j){
    for(int i = 0; i < n; ++i){
    if(field[i][j] == '*'){
    y[i][j] = tot;if(i + 1 == n)++tot;}else if(field[i][j] == '.'){
    if(i - 1 >= 0 && field[i - 1][j] == '*')++tot;}}}y_cnt = tot;int left, right;for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j){
    if(field[i][j] == '*'){
    left = x[i][j], right = y[i][j];a[left][right] = 1;}}
}bool dfs(int x)
{
    for(int y = 1; y <= y_cnt; ++y){
    if(!a[x][y] || vis[y])continue;vis[y] = true;if(!match[y] || dfs(match[y])){
    match[y] = x;return true;}}return false;
}int main()
{
    scanf("%d%d", &n, &m);for(int i = 0; i < n; ++i){
    scanf("%s", field[i]);}init();int ans = 0;for(int i = 1; i <= x_cnt; ++i){
    memset(vis, 0, sizeof vis);if(dfs(i))++ans;}printf("%d\n", ans);return 0;
}/* 4 4 *.*. .*** ***. ..*. *//* 4 */