【二分图匹配】Fire Net HDU - 1045

系统管理员 2022-06-04 01:40 168阅读 0赞

Think:  
1知识点：二分图匹配  
2题意：给定一个n\*n(n <= 4)的地图，需要建造地堡，若同一行或者同一列若出现多个地堡则每个地堡之间至少存在一堵墙间隔，询问最多可以建造多少个地堡  
3思路：  
（1）：分别对于行的方向和列的方向缩点成块并重新编号，然后根据新的X和Y集合建立新的图，进而二分图匹配即可  
4反思：  
（1）：对于特定问题如何建图需要加深感悟

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    char gra[14][14];
    int nx, ny;
    int x[14][14], y[14][14], xy[14][14];
    int match[104], vis[104];
    
    int dfs(int u);
    int mat_p();
    
    int main(){
        int n, i, j;
        while(~scanf("%d", &n) && n){
            for(i = 0; i < n; i++){
                scanf("%s", gra[i]);
            }
            memset(x, -1, sizeof(x));
            memset(y, -1, sizeof(y));
            /*行方向缩点成块,为块编号*/
            nx = 0;
            for(i = 0; i < n; i++){
                for(j = 0; j < n; j++){
                    while(gra[i][j] == 'X' && j < n){
                        j++;
                    }
                    if(j == n) continue;
                    nx++;
                    while(gra[i][j] == '.' && j < n){
                        x[i][j] = nx;
                        j++;
                    }
                }
            }
            /*列方向缩点成块，为块编号*/
            ny = 0;
            for(j = 0; j < n; j++){
                for(i = 0; i < n; i++){
                    while(gra[i][j] == 'X' && i < n){
                        i++;
                    }
                    if(i == n) continue;
                    ny++;
                    while(gra[i][j] == '.' && i < n){
                        y[i][j] = ny;
                        i++;
                    }
                }
            }
            /*通过行方向集合和列方向集合重新建图*/
            memset(xy, 0, sizeof(xy));
            for(i = 0; i < n; i++){
                for(j = 0; j < n; j++){
                    if(x[i][j] != -1 && y[i][j] != -1){
                        xy[x[i][j]][y[i][j]] = 1;
                    }
                }
            }
            /*通过匈牙利算法求最大匹配数*/
            printf("%d\n", mat_p());
        }
        return 0;
    }
    int mat_p(){
        int sum = 0;
        memset(match, 0, sizeof(match));
        for(int i = 1; i <= nx; i++){
            memset(vis, 0, sizeof(vis));
            if(dfs(i)) sum++;
        }
        return sum;
    }
    int dfs(int u){
        for(int i = 1; i <= ny; i++){
            if(!vis[i] && xy[u][i]){
                vis[i] = 1;
                if(match[i] == 0 || dfs(match[i])){
                    match[i] = u;
                    return 1;
                }
            }
        }
        return 0;
    }

[vjudge]: https://vjudge.net/problem/HDU-1045