HDU 1045 (0ms运行时间，傻B似的建图方法)

﹏ヽ暗。殇╰゛Y 2023-06-10 12:27 7阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1045

题目分析：  
看到网上博客，大都是缩点建图或者是枚举状压之类。  
而我的想法是根据行列进行建图，ch6802是这个题的简单版。 我看了ch6802的题解之后， 发现这个题用ch6802的方法一样可以建图，知识麻烦一点。 便想试一下，我首先按列给图中空地打了标记。 这些标记便是建图时候的y点。然后，遍历整个图，进行建图。 遍历时，时刻更新行结点。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int n;
    char str[5][6];
    int head[100],Next[100],ver[100];
    int match[100],visit[100],tot,top;
    void add(int x,int y)
    { 
        ver[++ top] = y; Next[top] = head[x]; head[x] = top;
        //ver[++ top] = x; Next[top] = head[y]; head[y] = top;
    }
    void init()
    { 
        tot = 2 * n; top = 0;
        for(int i = 0; i < 100; i ++){ 
            head[i] = Next[i] = ver[i] = 0;
            match[i] = visit[i] = 0;
        }
    }
    bool dfs(int x)
    { 
        for(int i = head[x],y; i; i = Next[i])
        if(!visit[y = ver[i]] && y != x){ 
            visit[y] = 1;
            if(!match[y] || dfs(match[y])){ 
                match[y] = x; return true;
            }
        }
        return false;
    }
    int main()
    { 
        while(~scanf("%d",&n) && n)
        { 
            init();
            for(int i = 1; i <= n;i ++)
                scanf("%s",str[i] + 1);
            int digit[6][6],limit = 1;memset(digit,0,sizeof(digit));
            for(int i = 1; i <= n; i ++)
                { 
                    int j = 1; while(str[j][i] == 'X' && j <= n) j ++;
                    int mark = 0;
                    for(; j <= n;)
                    { 
                        if(str[j][i] == '.')
                            digit[j][i] = limit,j ++,mark = 1;
                        else
                        { 
                            while(str[j][i] == 'X' && j <= n) j ++;
                            if(j <= n)
                            limit ++;
                        }
                    }
                    if(mark == 1) limit ++;
                }
            /*for(int i = 1; i<= n; i ++) {for(int j = 1;j <= n; j ++) printf("%d ",digit[i][j]); printf("\n"); }*/
            tot = n + limit;
            for(int i = 1; i <= n;i ++)
                { 
                    int x = i;int cnt = 0; int X = tot;
                    int j = 1;
                    while(str[i][j] == 'X') j ++;
                    for(; j <= n; j ++)
                    { 
                        int mark = 0;
                        while(str[i][j] == 'X' && j <= n)
                            { 
                                j ++;
                                if(mark == 0)
                                    cnt ++;
                                mark = 1;
                                if(j == n + 1) cnt --;
                            }
                        if(j > n) break;
                        if(str[i][j] == '.' && cnt == 0)
                            add(x,n + digit[i][j]);
                        if(cnt != 0)
                        { 
                            int y = X + cnt;
                            add(y,n + digit[i][j]);
                        }
                    }
                    tot += cnt;
                }
            int ans = 0;
            for(int i = 1; i <= tot; i ++){ 
                memset(visit,0,sizeof(visit));
                if(dfs(i)) ans ++;
            }
            printf("%d\n",ans);
           /*for(int i = 1; i <= tot; i ++) { printf("%d : ",i); for(int j = head[i]; j; j = Next[j]) printf("%d ",ver[j]); printf("\n"); }*/
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/