第十一届蓝桥杯大赛第二场省赛试题 C&C++ 研究生组-七段码

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48