POJ 2226 Muddy Fields（二分图匹配）

题目链接：2226 -- Muddy Fields

这道题与POJ 3041非常相似，POJ 3041的意思是找到最少的板子将“X”点全部盖上，这道题与3041唯一的不同就是3041可以盖空的点，而这道题不能。

比如下面一组样例

1 2

*.*

正确的输出应该是2，而按照3041的做法得到的答案是1.

所以这道题正确的做法是将同一行、同一列的点分散到不同的行和列上。

比如样例这组数据，首先我们按照行序从左到右横向遍历，属于同一块的点标上相同序号。结果记为r。

然后按照列序从上到下纵向遍历，属于同一块的标上相同的序号，结果记为c。

两次遍历结束后，原来位于（i，j）的点现在位于（r[i][j]，c[i][j]），现在图中的点已经分散开了，也就是说，每一行、每一列都只会出现一块连续的泥地。

然后就可以按照POJ 3041的做法做了。行号为一个集合，列号为另一个集合，交点为边，求最大点覆盖，也就是最大匹配边数。

#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define FIN freopen("in.txt", "r", stdin);
#define FOUT freopen("out.txt", "w", stdout);
const int INF = 0x3f3f3f3f;

//数组要开大一点
const int MAXN = 900;

int n, m, nn, mm, partner[MAXN << 1], rr[MAXN][MAXN], cc[MAXN][MAXN];
bool check[MAXN << 1], exist[MAXN][MAXN];
char area[MAXN][MAXN];

bool dfs(int cur)
{
    for (int i = 0 + nn; i < mm + nn; i++)
    {
        if (!check[i] && exist[cur][i - nn])
        {
            check[i] = true;
            if (partner[i] == -1 || dfs(partner[i]))
            {
                partner[cur] = i;
                partner[i] = cur;
                return true;
            }
        }
    }
    return false;
}

int hungray()
{
    memset(partner, -1, sizeof(partner));
    int ret = 0;
    for (int i = 0; i < nn; i++)
    {
        if (partner[i] == -1)
        {
            memset(check, false, sizeof(check));
            check[i] = true;
            if (dfs(i))
                ret++;
        }
    }
    return ret;
}

int main()
{
#ifndef ONLINE_JUDGE
    FIN;
#endif // ONLINE_JUDGE
    while (~scanf("%d%d", &n, &m))
    {
        memset(exist, false, sizeof(exist));
        memset(rr, 0, sizeof(rr));
        memset(cc, 0, sizeof(cc));
        for (int i = 0; i < n; i++)
            scanf("%s", area[i]);

        //横向标记
        bool flag = false;
        int cnt = 1;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (area[i][j] == '*')
                {
                    rr[i][j] = cnt;
                    flag = true;
                }
                else
                {
                    if (flag)
                    {
                        cnt++;
                        flag = false;
                    }
                }
            }
            if (flag)
            {
                cnt++;
                flag = false;
            }
        }
        nn = cnt;
        //纵向标记
        flag = false;
        cnt = 1;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (area[j][i] == '*')
                {
                    cc[j][i] = cnt;
                    flag = true;
                }
                else
                {
                    if (flag)
                    {
                        cnt++;
                        flag = false;
                    }
                }
            }
            if (flag)
            {
                cnt++;
                flag = false;
            }
        }
        mm = cnt;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (area[i][j] == '*')
                    exist[rr[i][j]][cc[i][j]] = true;
        printf("%d\n", hungray());
    }
    return 0;
}