POJ2226.md

二分图匹配，对于每一行中连续的''给出一个标号，每一列中连续的''给出一个标号，最终每个'*'都会有两个标号，要么是沿着x轴覆盖，要么是沿着y轴被 覆盖，所以这两个编号连一条边，然后跑最小顶点覆盖即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 1111;
int match[MAXN],vis[MAXN],n,m,xid[MAXN][MAXN],yid[MAXN][MAXN];
char s[MAXN][MAXN];
vector<int> G[MAXN];
bool dfs(int u){
    vis[u] = true;
    for(int i = 0; i < (int)G[u].size(); i++){
        int v = G[u][i];
        if(match[v]==-1||(!vis[match[v]]&&dfs(match[v]))){
            match[v] = u;
            return true;
        }
    }
    return false;
}
int hungary(int nn){
    int tot = 0;
    memset(match,255,sizeof(match));
    for(int i = 1; i <= nn; i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i)) tot++;
    }
    return tot;
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i = 1; i < MAXN; i++) G[i].clear();
        for(int i = 1; i <= n; i++) scanf("%s",s[i]+1);
        int ID = 0;
        for(int i = 1; i <= n; i++){
            int j = 1;
            while(j<=m){
                while(s[i][j]=='.') j++;
                if(j>m) break;
                ID++;
                while(s[i][j]=='*') xid[i][j] = ID, j++;
            }
        }
        int nn = ID;
        ID = 0;
        for(int i = 1; i <= m; i++){
            int j = 1;
            while(j<=n){
                while(s[j][i]=='.') j++;
                if(j>n) break;
                ID++;
                while(s[j][i]=='*') yid[j][i] = ID, j++;
            }
        }
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(s[i][j]=='*') G[xid[i][j]].push_back(yid[i][j]);
        printf("%d\n",hungary(nn));
    }
    return 0;
}