您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

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

不牌不改 发布时间:2021-08-18 23:18:20 ,浏览量:0

题目

题目链接

题解

暴力DFS。

没想到直接暴力DFS就行。

暴力选边,对于每条边可以选择选,也可以选择不选;

dfs过程可以有两种方式: 其一:每次选此边时都先判断一下,选了此边会不会成环,若成环,则不能选此边,若不会构成,则可以选此边。 其二:每次选边不进行判断,而是深搜到底且选取边的个数满足要求时,对全部被选的边进行判断,若不构成环则答案加一。 两种方式均可,第一种耗时少;两种方式分别对应代码1,代码2。

判断是否为环利用的是并查集的思想(有点类似于最小生成树的克鲁斯卡尔算法): 第一种方式中判断是否构成环,判断搜索到的边的两个端点是否具有相同的根,若具有则不可以选此边,若不具有相同根,则进行类似于并查集中join函数的操作,注意在dfs完后回溯fa数组的值,这点尤其关键,而且不可以在find函数中进行路径压缩,会导致得不到正确答案(具体原因不知道,因为模拟这个回溯过程太难了,如果有大佬有简单易懂的方式去理解,望不吝赐教) 第二种方式中,我们只需要在遍历全部被选中的边,判断是否存在同根的情况,若不存在则调用join函数,若存在则直接返回就行了,这种选法肯定是不对的;这里的join可以压缩。

两个代码的存储方式是一模一样的,理解了其中一个另一个很好理解。

代码1
#include
#define a first
#define b second
using namespace std;
typedef pair PII;
const int N = 1e6+10;

int n, m, ans, flag[N], fa[N], pnum;
vector edge;
char ch;

int find(int x) { 
	int r = x;
	while(r!=fa[r]) r = fa[r];
	return r;
}

void dfs(int id, int sum) { // id表示边在edge中的索引, sum表示已选边的个数
	
	if(id == edge.size()) {
		if(sum == pnum - 1) ans ++; // 构成一棵树了 
		return ;
	}
	
	// 选 
	int x = edge[id].a, y = edge[id].b;
	int rx = find(x), ry = find(y);
	if(rx != ry) { // 添加此边并不会构成环 
		int rrx = fa[rx];
		fa[rx] = ry; // 其实就是并查集中的join函数 
		dfs(id+1, sum+1);
		fa[rx] = rrx; // 对join函数的操作进行回溯 
	} 
	
	// 不选 
	dfs(id+1, sum);
}

int main()
{
	cin>>n>>m;
	for(int i = 0;i ch;
		int cur = i*m+j; // 点的编号 
		fa[cur] = cur; // 初始化fa数组 
		if(ch == 'E') {
			pnum ++; // number of point E 点E的个数 
			flag[cur] = 1; // flag[i]=1表明编号为i的位置为E 
			int left = (i-1)*m+j, up = i*m+j-1; // left:(i-1, j)的编号  up:(i,j-1)的编号 
			if(i > 0 && flag[left]) edge.push_back(PII(left, cur)); // 未发生越界,并且(i-1, j)位置上为E,则将边(i-1,j)--(i,j)添加进去 
			if(j > 0 && flag[up]) edge.push_back(PII(up, cur)); // 未发生越界,并且(i, j-1)位置上为E,则将边(i,j-1)--(i,j)添加进去 
		} 
	}	
	
	dfs(0, 0); 

	cout             
关注
打赏
1662186765
查看更多评论
0.0835s