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

1121 阅读 12 评论 0 点赞

> 前言：首先需要说明，我这份代码提交后答案错误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分

2 人评分

本文分类：题解列表
浏览次数：1121 次浏览
发布日期：2020-02-09 22:04:04
本文链接：https://blog.dotcpp.com/a/65771

上一篇 > 蓝桥杯2013年第四届真题-幸运数-题解(C++代码) by Zfans.
下一篇 > 蓝桥杯基础练习VIP-字符串对比-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 12 条评论

Dripping 4年前回复TA

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

JakeLin 4年前回复TA

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

JakeLin 4年前回复TA

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

1421 4年前回复TA

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

1421 4年前回复TA

热乎的题解

JakeLin 4年前回复TA

@列公子 @lielielie 看到了，很棒，谢谢！

JakeLin 4年前回复TA

@列公子 看到了，很棒，谢谢！

列公子 4年前回复TA

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

JakeLin 4年前回复TA

@列公子 思路相同

JakeLin 4年前回复TA

@列公子 对，我就是这个问题

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 12 条评论

发表评论 取消回复

评论列表共有 12 条评论

发表评论取消回复