Fire Net HDU - 1045 (二分图匹配)

题意：

给出一张图，图中'X'表示wall,'.'表示空地,可以放置blockhouse同一条直线上只能有一个blockhouse，除非有wall

隔开，问在给出的图中最多能放置多少个blockhous

分析：

把原始图分别按行和列缩点
建图：横竖分区。先看每一列，同一列相连的空地同时看成一个点，显然这样的区域不能够同时放两个点。这些

点作为二分图的X部。同理在对所有的行用相同的方法缩点，作为Y部。
连边的条件是两个区域有相交部分(即'.'的地方)。最后求最大匹配就是答案。

#include <bits/stdc++.h>

using namespace std;

int n;

struct node

{

    int a =  , b = ;

};

node id[][];

char mp[][];

bool link[][];

bool vis[];

int use[];

int hcnt,rcnt;

void dfsh(int x,int y){

    if(y <= n && mp[x][y] == '.'){

        id[x][y].a = hcnt;

        dfsh(x,y+);

    }

}

void dfsr(int x,int y){

    if(x <= n && mp[x][y] == '.'){

        id[x][y].b = rcnt;

        dfsr(x+,y);

    }

}

int find(int x)

{

    for (int s = ; s < rcnt; s++) {

        if (link[x][s] && !vis[s]) {

            vis[s] = ;

            if (use[s] ==  || find(use[s])) {

                use[s] = x;

                return ;

            }

        }

    }

    return ;

}

int main(int argc, char const *argv[])

{

    while(cin >> n && n){

        for(int i = ;i <= n ;i ++){

            cin >> mp[i] + ;

        }

            memset(id,,sizeof id);

            memset(link,,sizeof link);

            memset(use,,sizeof use);

            hcnt = rcnt = ;

            for(int i = ;i <= n;i ++){

                for(int j = ;j <= n ;j ++){

                    if(mp[i][j] == 'X'){

                        continue;

                    }

                    if(id[i][j].a == ){

                        dfsh(i,j);

                        hcnt ++;

                    }

                    if(id[i][j].b == ){

                        dfsr(i,j);

                        rcnt ++;

                    }

                    link[id[i][j].a][id[i][j].b] = ;

                }

            }

            int sum = ;

            for(int i = ;i < hcnt;i ++){

                memset(vis,,sizeof vis);

                if(find(i)) sum ++;

            }

            printf("%d\n",sum );

        }

    return ;

}

巴特西

Fire Net HDU - 1045 (二分图匹配)

最新文章

热门文章