题目
题目链接
题解暴力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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?