[蓝桥杯][算法提高VIP]传染病控制

题目

题目链接

题解

DFS。

大致思路： 按层深搜，遍历每一层中被感染的，将其直接子节点全部设置为被感染，统计被感染的数目，每次深搜的时候，我们只需要选定其中一个直接子节点作为截断处，将此结点设置为未被感染，进行深搜。回溯的时候再将标记再恢复为感染，恢复被感染的数目。当到达最深层时，更新最优解。

注意剪枝，要不超时。

有点难，虽然看题解看懂了，但是感觉理解的不透彻。

代码

#include
using namespace std;
const int N = 310;

int a, b, n, p, ans = N, ill[N], fa[N];
vector v[N], dp[N];

// 构建dp和fa 
void getdp(int x, int f, int d) { // x：点编号  f：x的父节点编号  d：深度 
	dp[d].push_back(x); // 深度为d的结点中包含x 
	fa[x] = f; // x的父亲是f 
	for(int i = 0;i >b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	getdp(1, 0, 1); 
	
	ill[1] = 1;
	dfs(1, 1);
	
	cout