#include<iostream>
using namespace std;
const int N = 10, M = 7;
int e[N][N] = {0}, f[N], open[N];//e[i][j]表示i和j之间是否连通;f[i]表示结点i的父节点;open[i] 1表示结点i打开,0表示关闭
long long ans = 0;
int find(int x){
if(f[x] == x) return x;
return f[x] = find(f[x]); //压缩路径
}
void dfs(int n){
if(n == 8){
for(int i = 1; i <= M; i++) {
f[i] = i;//并查集初始化,每个结点各为一个集合
}
for(int i = 1; i <= M; i++){
for(int j = 1; j <= M; j++){
if(e[i][j] && open[i] && open[j]){//连通则合并
f[find(i)] = find(j);
}
}
}
int cnt = 0;//当前方案中的连通块有几个
for(int i = 1; i <= M; i++){
if(open[i] && f[i] == i) cnt++;
}
if(cnt == 1) ans++;//只有一个连通块,则为合法方案
return;
}
open[n] = 1;//打开二极管n
dfs(n + 1);
open[n] = 0;//关闭二极管n
dfs(n + 1);
}
int main(){
e[1][2] = e[1][6] = 1;//把二极管视为顶点,是否连通视为之间是否有边
e[2][1] = e[2][3] = e[2][7] = 1;
e[3][2] = e[3][7] = e[3][4] = 1;
e[4][3] = e[4][5] = 1;
e[5][4] = e[5][7] = e[5][6] = 1;
e[6][1] = e[6][7] = e[6][5] = 1;
e[7][2] = e[7][3] = e[7][6] = e[7][5] = 1;
dfs(1);
cout << ans;
return 0;
}
第十一届蓝桥杯大赛第二场省赛试题 C&C++ 研究生组-七段码
2024-04-12 12:46:04 17 阅读