思想

1 按照行列，分别将每个联通块用一个编号表示
2 因为具备二分图性质，所以套模板即可
3 奇怪的是，我把我的代码最后的
“for(int i = 0;i <= cnt2;i)
{
memset(st,0,sizeof st);
if(find(i))
{
res;
}
}”中cnt2改成cnt1，建边方式也换一下后，最后一个样例过不去？有大佬知道为什么的话，私信我哦。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010,M = 10000010;
char g[N][N];
bool s[N][N],st[N * 1000];
int n,m,match[N * 1000];
int cnt1,cnt2,e[M],ne[M],h[M],idx;
int a[N][N],b[N][N];
int fla[N];

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

bool find(int x)
{
    for(int i = h[x];i != -1;i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;i++)
    {
        cin >> g[i];
    }
    memset(h,-1,sizeof h);
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            if(g[i][j] == '*')
            {
                a[i][j] = cnt1;
                fla[cnt1] = -1;
            }
            else
            {
                cnt1++;
            }
        }
        cnt1++;
    }
    for(int i = 0;i < m;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(g[j][i] == '*')
            {
                b[j][i] = cnt2;
            }
            else
            {
                cnt2++;
            }
        }
        cnt2++;
    }
    for(int i = 0;i < n;i++)
     for(int j = 0;j < m;j++)
     {
         if(g[i][j] == '*')
         {
             add(b[i][j],a[i][j]);
         }
     }
    int res = 0;
    for(int i = 0;i < cnt2;i++)
    {
        memset(st,0,sizeof st);
        if(find(i))
        {
            res++;
        }
    }
    cout << res << endl;
    return 0;
}