JakeLin

用户名：jake546

访问量：43183

签　名：

腾讯需要我！

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

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-1581题-蓝桥杯算法提高VIP-密码锁-题解(C++代码)-BFS
浏览：346

JakeLin-几种排序算法代码小记（插入/选择/快速/归并/冒泡/更新中...）
浏览：376

JakeLin-1745题-继续畅通工程-题解(C++代码)-简单易懂
浏览：314

你可能喜欢

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

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

　　作者: JakeLin　　　　发表时间：2020-02-09 22:04:04 浏览：1047　|　评论：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

1421 2020-02-17 19:41:53 |

有没有不删掉一层的最大节点，最后感染总数比删除的要少

JakeLin 2020-02-17 23:12:28 |

是的，楼下的大佬提供了一个贪心法不可解决的例子，可以康康 https://blog.dotcpp.com/a/65913

JakeLin 2020-02-17 23:12:45 |

@ZCGU20180341421 是的，楼下的大佬提供了一个贪心法不可解决的例子，可以康康 https://blog.dotcpp.com/a/65913

列公子

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

2020-02-12 15:17:30

JakeLin 2020-02-12 16:46:22 |

对，我就是这个问题

JakeLin 2020-02-12 16:46:34 |

思路相同

列公子 2020-02-13 15:25:31 |

@jake546 我唯一的那篇文章里，加了一个不能用贪心的例子

JakeLin 2020-02-13 17:31:47 |

看到了，很棒，谢谢！

JakeLin 2020-02-13 17:32:06 |

@lielielie 看到了，很棒，谢谢！

JakeLin

救救孩子，救救孩子TAT

2020-02-09 22:06:08

JakeLin

TA的其他文章

你可能喜欢

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

C二级辅导-阶乘数列（C语言代码）

整除问题（C语言代码）

假币问题（C++代码）（向上取整的一种处理方式）

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

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

评论区

精彩推荐

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

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

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

WU-小九九（C++代码）

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

字符逆序（C语言代码）

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

前10名（C语言代码）

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

JakeLin

TA的其他文章

你可能喜欢

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

C二级辅导-阶乘数列 （C语言代码）

整除问题 （C语言代码）

假币问题 （C++代码）（向上取整的一种处理方式）

C语言训练-尼科彻斯定理 （C语言代码）。。。内含证明定理

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

评论区

精彩推荐

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

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

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

WU-小九九 （C++代码）

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

字符逆序 （C语言代码）

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

前10名 （C语言代码）

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

C二级辅导-阶乘数列（C语言代码）

整除问题（C语言代码）

假币问题（C++代码）（向上取整的一种处理方式）

C语言训练-尼科彻斯定理（C语言代码）。。。内含证明定理

　　评论区

WU-小九九（C++代码）

字符逆序（C语言代码）

前10名（C语言代码）