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

题目

题目链接

题解

暴力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