列公子

用户名：lielielie

访问量：9584

签　名：

等　　级
排　　名	1720
经　　验	2590
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

1924题 - 01背包 - 动态规划 + 一维数组空间优化
浏览：485

你可能喜欢

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

[1495] 传染病控制 ( C++ 语言, DFS 方法 )

　　作者: 列公子　　　　发表时间：2020-02-11 22:46:03 浏览：820　|　评论：5　

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

# [1495] 传染病控制 ( C++ 语言, DFS 方法 )
## 1. 问题转化
1. 所有结点构成一棵树，在树的**每一层**摘除一个节点(及其子节点)，使得**保留的树, 其节点数最小**，即感染的人数最少。
2. 也就是尽可能多地 去掉树中的节点。

## 2. 数据结构
1. 树采用**邻接表**存储, 即 ```vector<int> Adj[maxn]```, 使用邻接矩阵 超时 18 %
2. 用一个类似邻接表的结构, 存储树中每一层有哪些节点 (存储其编号), 即 ```vec<int> depths```
3. 布尔型数组 ```bool isRemoved[maxn]``` 标记对应编号的节点**是否已被摘除**。

## 3. 算法
1. ```initDepths```用来初始化 ```depths```, 即递归地求每个节点的深度。
2. ```changeState``` 用来**摘除节点**(及其子节点) 或 **恢复节点**(及其子节点), 通过递归地操作 ```isRemoved``` 数组实现, 同时统计该子树的节点总数。
3. ```dfs``` 深度优先地搜索 树的每一层

## 4. 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 1495 传染病控制
// 在树的每一层摘除一条边, 使得在摘除后的树中, 结点数最小; 亦即摘除的结点数最大
// 使用 DFS, 不能贪心
//
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 310;
int N, P;      // 结点数. 边数

bool isRemoved[maxn];      // 各个结点是否被剪掉了
vector<int> G[maxn];      // 邻接表
vector<int> depths[maxn];    // 每一层有哪些编号的结点  depth[2] 为树的第二层有哪些结点

void initDepths(int layer, int node){       // 初始化 depths
    depths[layer].push_back(node);

for (int v = 0; v < G[node].size(); v ++){
        int cur = G[node][v];
        initDepths(layer + 1, cur);
    }
}

int changeState(int num, bool state){       // 将编号为 num 的所有子节点 的 isRemoved 置为 state
    int sum = 1;        // 处理的所有结点数, 可能是剪去/加上
    isRemoved[num] = state;

for (int i = 0; i < G[num].size(); i++)
        sum += changeState(G[num][i], state);
    return sum;
}

int ans = 0;    // 从树中摘除的结点数 最大值

void dfs(int layer, int tot){
    ans = max(ans, tot);
    // 逐个遍历该层节点
    for (int v = 0; v < depths[layer].size(); v++){
        int cur = depths[layer][v];

if (!isRemoved[cur]) {
            int val = changeState(cur, true);  // 摘去的节点数
            dfs(layer + 1, tot + val);
            changeState(cur, false);        // 回溯
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(isRemoved, 0, sizeof(isRemoved));

cin >> N >> P;
    for (int i = 0; i < P; i++){
        int a, b;
        cin >> a >> b;
        if (a > b)
            swap(a, b);
        G[a].push_back(b);
    }

initDepths(1, 1);
    dfs(2, 0);

cout << N - ans << "\n";        // 计算剩余的节点数
    return 0;
}
```
## 5. 为什么不能用贪心
考虑这样的一颗树：
![不能用贪心的树](/image_editor_upload/20200213032139_99083.jpg "不能用贪心的树")
## 6. 参考的解答
参考了以下解答, 在此表示感谢。
[解答1](https://blog.csdn.net/zvenWang/article/details/87970374)
[解答2](https://blog.csdn.net/Eric1561759334/article/details/82502078)

0.0分

5 人评分

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

编程语言转换

万能编程问答

代码解释器

　　评论区

flags

这组数据似乎通不过啊7 6 1 6 1 7 6 2 6 3 7 4 7 5

2021-03-11 14:21:34

Emilia

简单易懂的回溯，可以的

2020-11-25 15:17:07

一起闹〆朱瑞晗

牛逼

2020-05-09 21:55:17

陈子昂

代码太棒了！！！

2020-05-06 21:59:57

JakeLin

理解了，很棒！！！

2020-02-13 17:32:25

列公子

TA的其他文章

你可能喜欢

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

假币问题（C语言代码）

校门外的树（C语言代码）

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

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

[1495] 传染病控制 ( C++ 语言, DFS 方法 )

评论区

精彩推荐

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

WU-拆分位数（C++代码）

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

1009题解

计算质因子（C语言代码）

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

多输入输出练习2 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

马拦过河卒（C语言代码）

母牛的故事（C语言代码）

列公子

TA的其他文章

你可能喜欢

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

假币问题 （C语言代码）

校门外的树 （C语言代码）

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

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

[1495] 传染病控制 ( C++ 语言, DFS 方法 )

评论区

精彩推荐

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

WU-拆分位数 （C++代码）

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

1009题解

计算质因子 （C语言代码）

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

多输入输出练习2 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

马拦过河卒 （C语言代码）

母牛的故事 （C语言代码）

假币问题（C语言代码）

校门外的树（C语言代码）

　　评论区

WU-拆分位数（C++代码）

计算质因子（C语言代码）

马拦过河卒（C语言代码）

母牛的故事（C语言代码）