【2020年省赛B组】试题E: 七段码

题解

答案为：80

我们可以把每个二极管看成一条边，并把相邻的边相连，那么这样题目就可以转换为: 有多少种选边方案，使得选出来的边构成的图只有一个联通快。 于是现在只要枚举选边方案，再判断联通块的个数是否为1即可

1. 枚举选边方案可以采用状压(当然直接 dfs 搜索也行):用二进制 1、0 分别表示二进制位所对应的边是选还是不选，复杂度为$2^7$
2. 求联通块的个数可以采用 bfs(也可以采用并査集等方法):从任意一个选中的边出发将所有能到达的选中的边全部打上标记:若标记覆着了所有选中的边则联通块只有一个(满足条件)，反之不止一个联通块(不满足条件)。 最后的答案为 80。

#include<bits/stdc++.h>
using namespace std;
int ans , g[7][7] , vis[7] , flag[7];
void bfs(int x){
    queue<int>que;
    que.push(x);
    vis[x] = true;
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int i = 0 ; i <= 6 ; i ++){
            if(g[u][i] && flag[i] && !vis[i]){
                vis[i] = true;
                que.push(i);
            }
        }
    }
}
bool check(int x){
    for(int i = 0 ; i <= 6 ; i ++) flag[i] = vis[i] = false;
    int cnt = 0;
    for(int i = 6 ; ~i ; i --) if(x >> i & 1) flag[i] = true;
    for(int i = 0 ; i <= 6 ; i ++){
        if(flag[i] && !vis[i]){
            bfs(i);
            cnt ++ ;
        }
    }
    return cnt == 1;
}
signed main()
{
    g[0][1] = g[0][5] = 1;
    g[1][0] = g[1][2] = g[1][6] = 1;
    g[2][1] = g[2][3] = g[2][6] = 1;
    g[3][2] = g[3][4] = 1;
    g[4][3] = g[4][5] = g[4][6] = 1;
    g[5][0] = g[5][4] = g[5][6] = 1;
    g[6][1] = g[6][2] = g[6][4] = g[6][5] = 1;
    for(int i = 0 ; i < (1 << 7) ; i ++){
        if(check(i)) {
            ans ++ ;
        }
    }
    cout << ans << '\n';
    return 0;
}