JakeLin

用户名：jake546

访问量：38448

签　名：

腾讯需要我！

等　　级
排　　名	39
经　　验	12639
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-题解1124：C语言训练-大、小写问题（C++代码）
浏览：383

JakeLin-1523题-蓝桥杯算法提高VIP-打水问题-题解(C/C++代码)
浏览：445

JakeLin-1568题-身份证排序-题解(C++代码)-结构体排序/没有用字符串函数
浏览：495

你可能喜欢

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

JakeLin-1495题-传染病控制-题解(C++代码)-DFS+BFS

　　作者: JakeLin　　　　发表时间：2020-02-09 22:04:04 浏览：981　|　评论：4　

原题链接：蓝桥杯算法提高VIP-传染病控制

> 前言：首先需要说明，我这份代码提交后答案错误9%，但我百思不得其解，我认为思路是没有错的，看到这道题目题解较少，并且没有太多解释，所以想分享交流一下思路，这个思路相对其他题解比较简单，应该是有特殊情况没有考虑到，如果大佬们指出我的错误定感激不尽！

首先我们看一下题目给的例子图示：
![](/image_editor_upload/20200209093204_98982.png)
> 红色的X表示切断路径，红色的圈表示感染的人（有其他多种情况），结果为3

思路为：**每一层**只能切断一条路，要使得最后感染的人数最少。那么我切掉的应该是**节点数量多这一支**。**这应该很好理解：**因为每一层只能切掉一支，那我为了让感染的人尽量少，我就要切掉人多的这一支来保全更多的人

所以我可以通过**DFS**递归求出**以每个节点为根的树的节点数量**，它可以表示这棵树的大小。
又因为**BFS**的本质就是**层次遍历**，我可以通过**BFS**，**比较每一层中的节点哪棵树最大**，我要保全它，所以将其切断。

但是这个题目的例子比较简单，我们可以看看一个较复杂的例子：
![](/image_editor_upload/20200209094737_46255.png)
这棵树不一定是一棵二叉树，当我们**第一层切掉以2位根的子树**时，1还剩下两个儿子：3和8都会被感染，而接下来，我们需要比较3和8的孩子：**7,6,10,11，选择一个来切掉**，显然切掉6可以救活两个人，而切掉其他任一个都只能救下一个人，所以**将6切掉**，结果感染人数为6。

这就需要将BFS进行改装，我是这样做的：
- 建一个队列
- 1入队
- 1出队，比较它的孩子2 3 8，选出2，所以将剩下3 8入队
- 3,8都出队，比较它们的所有孩子7 6 10 11，选出6，将剩下的7 10 11入队
- 循环往复

------------

**以上就是我的思路，它的效率是可以的，但我不知道逻辑是否足够严谨，或者错误出在哪里（应该有一个样例出错），希望参考这个思路的大佬能够赐教，叩谢各位！希望武汉肺炎早日好转，武汉加油！中国加油！！！**

下面附上完整代码，代码写的不好，还望多多指教：
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 300 + 10;
vector<int> map[maxn];
int vis[maxn];
int son[maxn];
int tmp[maxn];
int cnt=0;
void CountSon(int n){  //计算以n为根的树的节点数量son[n]
	vis[n]=1;
	son[n]=1;
	for(int i=0;i<map[n].size();i++){
		if(vis[map[n][i]]==0){
			CountSon(map[n][i]);
			son[n]+=son[map[n][i]];
		}
	}
}
int sum=0;
void BFS(int n){
	vis[n]=1;
	sum++;
	queue<int> q;
	q.push(n);
	while(!q.empty()){
		while(!q.empty()){   //队中所有元素出队，因为他们属于同一层
			tmp[cnt++] = q.front();
			q.pop();
		}
		int mmax = 0;
		int tag=0;
		int index;
		for(int j=0;j<cnt;j++){  //比较同层次所有元素的所有孩子
			int u = tmp[j];
			for(int i=0;i<map[u].size();i++){
				if(vis[map[u][i]]==0){
					if(son[map[u][i]]>mmax){ //选出树最大的树，不访问抛弃掉
						mmax = son[map[u][i]];
						if(tag==0){
							tag++;
						}else{
							sum++;
							vis[index]=1;
							q.push(index);
						}
						index = map[u][i];
					}else{  //不是最大的树就访问：将节点入队
						sum++;
						vis[map[u][i]]=1;
						q.push(map[u][i]);
					}	
				}
			}			
		}
		cnt=0;
	}

}
int main(){
	int m,p;
	cin>>m>>p;
	while(p--){ //构建地图
		int a,b;
		cin>>a>>b;
		map[a].push_back(b);
		map[b].push_back(a);
	}
	CountSon(1);
	memset(vis,0,sizeof(vis));
	BFS(1);
	cout<<sum;
	return 0;
}
```

0.0分

7 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

Dripping

这样的贪心很明显就是错误的，题目没有说一定是二叉树，当然即使是二叉树采用该贪心算法也是错误的。
假设此时第二层中只有两个节点，如果第二层的右子树有100个节点，但是该右子树中每一层只有一个节点，此时第二层的左子树只有80个节点，但是左子树中除了根节点，其它节点全部在第三层中（即第三层有79个节点）
按照你的贪心策略，此时在第二层进行切断时会选择切断根节点与右子树的连接，但是正确答案应该是先切断与左子树的连接。

2020-08-06 21:48:39

1421

热乎的题解

2020-02-17 19:29:44

列公子

用贪心，在每一层删去 以该节点为根节点的子树的总节点数 最大 的那个节点，提交后答案错误9%  想不明白

2020-02-12 15:17:30

JakeLin

救救孩子，救救孩子TAT

2020-02-09 22:06:08

JakeLin

TA的其他文章

你可能喜欢

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

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

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

C语言训练-素数问题（C语言代码）

C二级辅导-同因查找（C语言代码）

JakeLin-1495题-传染病控制-题解(C++代码)-DFS+BFS

评论区

精彩推荐

校门外的树（C++代码）

小九九（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

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

C语言训练-斐波纳契数列（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

WU-格式化数据输出（C语言代码）

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

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

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

JakeLin

TA的其他文章

你可能喜欢

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

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

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

C语言训练-素数问题 （C语言代码）

C二级辅导-同因查找 （C语言代码）

JakeLin-1495题-传染病控制-题解(C++代码)-DFS+BFS

评论区

精彩推荐

校门外的树 （C++代码）

小九九 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C++代码）按照惯例的只有一行核心代码

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

C语言训练-斐波纳契数列 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

WU-格式化数据输出 （C语言代码）

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

【魔板】 （C++代码）(时间超限，希望会的帮我改正一下)

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

C语言训练-素数问题（C语言代码）

C二级辅导-同因查找（C语言代码）

　　评论区

校门外的树（C++代码）

小九九（C语言代码）

C语言训练-斐波纳契数列（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

WU-格式化数据输出（C语言代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)