目录
C++收集宝石
第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题
一、题目要求
1、编程实现
聪聪在玩冒险岛游戏，为了召唤法力更强大的神龙，他必须尽可能收集更多的魔法宝石，每颗宝石都有不同的功效。不过在游戏里，几乎每颗魔法宝石都会和另外一颗宝石相冲。相冲表示这两颗宝石不能同时拥有。
例如，宝石A和宝石B 相冲，那么，你可以选择两颗主石都不收集，也可以只收集宝石A 或者只收集宝石 B，但不能同时拥有宝石 A和宝石B现在给定了游戏里宝石的数量N(2≤N≤100)，宝石从1到N依次编号，并给出M对(2≤M≤2000)相冲的宝石编号，请帮聪聪计算出最多能够收集到多少颗宝石。
例如: N=6，M=8时，6颗宝石的编号分别为 1、2、3、4、5、6，其中有8对相冲的宝石，对应编号如下：
1 2
2 3
2 4
2 5
2 6
3 4
4 5
5 6这表示宝石1和宝石2相冲，宝石2和宝石3,4,5都相冲，宝石3和宝石4相冲，宝石4和宝石5相冲，宝石5和宝石6 相冲。
有三个方案收集到的宝石数量最多:(135)、(136)、(146)，这些方案里，最多收集到的宝石数量都是3，所以程序输出3。
2、输入输出
输入描述：第一行输入两个正整数N和 M(2≤N≤100，2≤M≤2000)，分别表示游戏里的宝石数量和 M 对相冲的宝石，两个正整数之间用一一个空格隔开。
接下来输入 M 行，每行两个正数，分别表示相冲的两颗宝石的编号，两个正整数之间用一个空格隔开
输出描述：只有一行，一个整数，即聪聪在游戏里最多能够收集到的宝石数量
输入样例：
6 8
1 2
2 3
2 4
2 5
2 6
3 4
4 5
5 6输出样例：
3
二、算法分析
- 从给定题目来看，稍微有点复杂，但其实这类题型学过算法的小朋友来说难度不会很大
- 这类型题（最多/最少/最长/最短）往往可以使用深度优先算法来解决
- 当然也可以使用其他的方法，方法有很多，小朋友们只要能实现题目功能即可
- DFS的思路是通过递归和回溯机制遍历每个宝石，求出最优解
三、程序编写
#include <iostream>
using namespace std;
int n, m, f[110][110], p[110], res;
void dfs(int step, int c)
{
if (res > c + n - step)
return;
if (step > n)
{
res = max(res, c);
return;
}
bool check = true;
for (int i = 1; i < step; i++)
if (p[i] && f[i][step]) //已选且有冲突
{
check = false;
break;
}
if (check) //可选
{
p[step] = 1;
dfs(step + 1, c + 1);
}
p[step] = 0;
dfs(step + 1, c);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
f[x][y] = 1; //宝石冲突
}
dfs(1, 0);
cout << res << endl;
return 0;
}四、程序说明
- 首先需要导入输入输出流头文件
- 然后是引入std命名空间中的所有成员到当前的程序中，这样在当前的程序中就可以直接使用 std 命名空间中的所有成员，而不需要使用的时候在成员前面加上（std::）前缀
- 定义几个全局变量，n和m表示宝石的数量和冲突关系的数量，f表示冲突关系的矩阵，p表示选中的宝石数组，res表示当前的最优解
- 定义一个递归函数dfs。函数的参数包括step表示当前的宝石编号，c表示已经选中的宝石数量
- 在dfs函数的开头，判断如果当前的最优解已经大于已经选中的宝石数量加上剩余的宝石数量，则退出递归。这是一个剪枝策略，可以减少递归的次数
- 接下来，判断如果已经遍历到了所有的宝石，则更新最优解并返回
- 否则，代码使用一个布尔变量check来判断当前的宝石是否可以选中
- 遍历之前的宝石，如果存在一个已经选中的宝石与当前宝石存在冲突关系，则将check设为false
- 如果check为true，表示当前的宝石可以选中
- 将p[step]设为1，表示选中当前的宝石，然后递归调用dfs函数，更新step和c的值
- 如果check为false，表示当前的宝石不能选中。将p[step]设为0，表示不选中当前的宝石，然后递归调用dfs函数，更新step和c的值
- 主函数main中，首先读入n和m的值
- 然后，根据冲突关系的数量，读入冲突关系，将f矩阵相应位置设为1
- 最后，调用dfs函数求解最优解，并输出结果
- 最后返回0，程序结束
本文作者：小兔子编程 作者首页：https://blog.csdn.net/frank2102
五、运行结果
6 8
1 2
2 3
2 4
2 5
2 6
3 4
4 5
5 6
3六、考点分析
难度级别：难，这题相对而言还是有一定的难度，具体主要考查如下：
- 充分掌握变量的定义和使用
- 深度优先算法的定义和使用
- 学会输入流对象cin的使用，从键盘读入相应的数据
- 学会for循环的使用，在确定循环次数的时候推荐使用学会
- 学会while循环的使用，在不确定循环次数的时候推荐使用
- 学会if条件判断语句的使用，满足一定条件才能执行后面的语句
- 学会if...else...双分支语句的使用，条件满足执行一种处理，不满足执行另一种处理
- 掌握输出流对象cout的使用，与流插入运算符 << 结合使用将对象输出到终端显示
- 学会分析题目，算法分析，将复杂问题模块化，简单化，从中找到相应的解题思路
- 充分掌握递归函数、分支语句、循环语句和深度优先算法知识的使用及输入输出的用法
PS：方式方法有多种，小朋友们只要能够达到题目要求即可！