Fire Net HDU - 1045

//只有出现墙的时候，才会出现一行/列多个点的情况
//那么可以考虑缩点，以行为例
//如果某一行没有墙，那么这一列整体所成一个点
//如果有墙，那么把没有墙的部分缩成一个点

//当换行时，记得点数++ 
#include<iostream>
#include<cstring> 
#define INF 0x3f3f3f3f
#define LL long long
const int N=1000+5;
using namespace std;
int n;
bool st[N];//vis[i]表示是否在交替路中
int match[N];//存储连接点
int g[N][N];//存边
char str[N][N];
int x[N][N],cntX;//行点集
int y[N][N],cntY;//列点集
bool find(int x) {
    for(int y=0; y<cntY; y++) { //对x的每个邻接点
        if(g[x][y]==1&&!st[y]) { //不在交替路中
            st[y]=true;//放入交替路
            if(match[y]==-1 || find(match[y])) { //如果是未匹配点，说明交替路是增广路
                match[y]=x;//交换路径
                return true;//返回成功
            }
        }
    }
    return false;//不存在增广路，返回失败
}
int hungarian() {
    int ans=0;//记录最大匹配数
    memset(match,-1,sizeof match);
    for(int i=1; i<=cntX; i++) { //从左侧开始每个结点找一次增广路
        memset(st,false,sizeof st);
        if(find(i))//找到一条增广路，形成一个新匹配
            ans++;
    }
    return ans;
}
int main() {

    while(scanf("%d",&n)!=EOF&&n) {
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        memset(g,false,sizeof(g));
        for(int i=0; i<n; i++)
            scanf("%s",str[i]);
        //对行缩点
        cntX=1;
        for(int i=0; i<n; i++) { 
            for(int j=0; j<n; j++) { 
                if(str[i][j]=='.')//同一区域
                    x[i][j]=cntX;
                if(str[i][j]=='X')//墙体阻隔
                    cntX++;
            }
            cntX++;//下一行
        }

        //对列缩点
        cntY=1;
        for(int j=0; j<n; j++) { 
            for(int i=0; i<n; i++) { 
                if(str[i][j]=='.')//同一区域
                    y[i][j]=cntY;
                if(str[i][j]=='X')//墙体阻隔
                    cntY++;
            }
            cntY++;//下一列
        }

        //连边
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(str[i][j]=='.')
                    g[x[i][j]][y[i][j]]=true;

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

Fire Net HDU - 1045

原文：https://www.cnblogs.com/QingyuYYYYY/p/12409549.html