lw

用户名：saudade

访问量：13789

签　名：

等　　级
排　　名	175
经　　验	6857
参赛次数	23
文章发表	25
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-士兵排队问题-题解（C++代码）拓扑+去重
浏览：854

蓝桥杯算法提高VIP-师座操作系统-题解（C语言代码）STL大法，map+string
浏览：227

素数求和-题解（C++代码）筛法求素数，遍历
浏览：281

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯2015年第六届真题-生成树计数-题解（C++代码）

　　作者: lw　　　　发表时间：2020-11-12 19:47:00 浏览：636　|　评论：0　

原题链接：蓝桥杯2015年第六届真题-生成树计数

### 111
##### 生成树，n个结点由n-1条边连接，不存在环，由于边没有权值，不需要prime或克鲁斯卡尔算法，选择，暴力枚举选边以后判断有无环即可
```cpp
#include <bits/stdc++.h>
#define mod 1000000007
typedef long long ll;
using namespace std;
int n, m, cnt, ans, kk;
char s[8][100005];
int vis[700000];
int flag[700000];
int fa[700000];
struct E {
	int u, v;
};
E e[1400000];

//路径压缩并查集
int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

//x:边的序号, pcnt:已连接的点的个数， ecnt:已选择的边数
void dfs(int x,int pcnt,int ecnt) {
	//遍历完所有的边
	if(x == cnt) {
		//点的个数与边的个数符合生成树特点
		if(pcnt == n * m - kk && ecnt == n * m - 1 - kk) {
			for(int i = 0; i <= n * m; i++) {
				fa[i] = i;	
			}
			//判断环
			for(int i = 0; i < cnt; i++) {
				if(flag[i] == 1) {
					int a = find(e[i].u);
					int b = find(e[i].v);
					if(a == b) {
						return ;//如果构成环路	
					}
					fa[a]=b;
				}
			}
			ans++;
		}
		return ;
	}
	int u = e[x].u, v = e[x].v;
	int k1 = vis[u], k2 = vis[v];

vis[u] = 1;
	vis[v] = 1;
	flag[x] = 1;
	//选择x这条边
	//pcnt+2-k1-k2表示要去除以及选择了的点
	dfs(x + 1, pcnt + 2 - k1 - k2, ecnt + 1);

vis[u] = k1;//注意这里的回溯
	vis[v] = k2;
	flag[x] = 0;

//不选择x这条边
	dfs(x + 1, pcnt, ecnt);
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> s[i];
	}	
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < m; j++) {
			//上下方向的边
			if(s[i][j] == 'E' && s[i + 1][j] == 'E') {
				//设置边的端点的序号
				e[cnt].u = (i - 1) * m + j + 1;
				e[cnt++].v = i * m + j + 1;
			}
			//左右方向的边
			if(s[i][j] == 'E' && s[i][j + 1] == 'E') {
				e[cnt].u = (i - 1) * m + j + 1;
				e[cnt++].v = (i - 1) * m + j + 2;
			}
			if(s[i][j] == 'N') {
				kk++; //统计为空的点
			}
		}
	}
	dfs(0, 0, 0);
	cout << ans;
	return 0;
}
```

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

lw

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

蓝桥杯2015年第六届真题-生成树计数-题解（C++代码）

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

【绝对值排序】（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

1113题解

1124题解

1128题解（返回值为数组的情况）

lw

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

蓝桥杯2015年第六届真题-生成树计数-题解（C++代码）

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

【绝对值排序】 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

1113题解

1124题解

1128题解（返回值为数组的情况）

C二级辅导-阶乘数列（C语言代码）

　　评论区

【绝对值排序】（C语言代码）