【蓝桥杯】雪地工程核弹引爆控制器最小数量计算
问题描述
危机纪元 2211 年,由罗辑领导的雪地工程正式进入部署,雪地工程中布置了大量的核弹,整个工程由信号中转站和起爆装置构成,形成了一棵具有 nn 个点 n−1n−1 条边的有根树,11 号点为根节点,树边为 (ui,vi)(ui,vi) 。
起爆装置为度为 11 并且不是根的节点,其余节点为信号中转站,预先在 mm 个起爆装置上面布置有核弹,为了引爆核弹,会在 11 号节点施加一个引爆信号,在信号中转站上,该信号会随机向某一个子节点传输,为了避免核弹不被引爆,你可以在信号中转站上面安装控制器,使得引爆信号只会往指定的子节点传输,为了减少开销,你能帮帮罗辑计算最少需要安装的控制器数量吗?
输入格式
第 11 行包含一个正整数 nn(2≤ n ≤ 1052≤ n ≤ 105),表示树点的数量。
第 2∼n+12∼n+1 行每行包含 22 个正整数 ui,viui,vi(1≤ui,vi≤n1≤ui,vi≤n),分别表示树边的两个端点。
接下来 11 行包含一个正整数 mm (1≤ m ≤1≤ m ≤ 叶子数量) ,表示含有核弹的起爆装置的数量。
再接下来 11 行包含 mm 个整数 , 表示具有核弹起爆装置的节点编号。
输出格式
输出一个数字,表示需要放置的最小控制器数量。
样例输入
5
1 2
1 3
1 4
2 5
2
4 5
样例输出
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> adj(n + 1); // 邻接表
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 构建树结构,确定父子关系
vector<int> parent(n + 1, 0);
vector<vector<int>> children(n + 1);
queue<int> q;
vector<bool> visited(n + 1, false);
q.push(1);
visited[1] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
parent[v] = u;
children[u].push_back(v);
q.push(v);
}
}
}
int m;
cin >> m;
unordered_set<int> bomb_set;
for (int i = 0; i < m; ++i) {
int b;
cin >> b;
bomb_set.insert(b);
}
vector<bool> has_bomb(n + 1, false);
for (int b : bomb_set) has_bomb[b] = true; // 标记核弹节点
// 后序遍历标记所有包含核弹的子树
stack<pair<int, bool>> st;
st.push({1, false});
while (!st.empty()) {
auto [u, processed] = st.top();
st.pop();
if (!processed) {
st.push({u, true});
// 逆序入栈以保证子节点按顺序处理
for (auto it = children[u].rbegin(); it != children[u].rend(); ++it)
st.push({*it, false});
} else {
for (int v : children[u]) {
if (has_bomb[v]) {
has_bomb[u] = true;
break; // 只要有一个子节点有炸弹,父节点即标记
}
}
}
}
int ans = 0;
for (int u = 1; u <= n; ++u) {
// 判断是否为信号中转站:根节点或非叶子非根节点
bool is_station = (u == 1) || (!children[u].empty());
if (is_station) {
int cnt = 0;
for (int v : children[u]) {
if (has_bomb[v]) cnt++;
}
ans += max(0, cnt - 1); // 需要控制器数为 cnt-1
}
}
cout << ans << endl;
return 0;
}
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 2s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
代码思路解析
-
输入处理与树构建
通过邻接表存储树结构,并用BFS确定父子关系,构建每个节点的子节点列表。 -
核弹标记
标记所有含有核弹的叶子节点。 -
后序遍历标记子树
从叶子节点向上回溯,标记每个节点的子树是否包含核弹。若某节点的子节点子树包含核弹,则该节点也被标记。 -
统计控制器数量
遍历每个信号中转站节点,统计其子节点中包含核弹的数目。若数目超过1,则需在该节点安装(数目-1)个控制器,确保信号正确传输。
关键点
-
信号中转站判断:根节点或非叶子节点。
-
后序遍历更新子树标记:确保父节点正确反映子树的核弹状态。
-
控制器计算:每个中转站需要控制器数为其包含核弹子节点数减一,确保最少干预。
题目详细解析
我们用一个具体例子理解题目:
样例输入:
5 1 2 1 3 1 4 2 5 2 4 5
关键逻辑
-
信号传播规则:
-
中转站(非叶子非根节点)默认随机选择一个子节点。
-
安装控制器后,中转站可以指定信号传递方向。
-
-
核心观察:
-
如果某个中转站的多个子节点的子树包含核弹,必须强制信号走向这些子节点。
-
控制器的作用是减少选择的不确定性,确保覆盖所有核弹。
-
-
解决方案:
-
统计每个中转站节点需要引导的子节点数量。
-
若某中转站有
k
个子节点的子树含核弹,则需k-1
个控制器。
-
代码分步解析
1. 邻接表构建与树的遍历
邻接表是树的标准存储方式,每个节点存储其直接连接的节点:
vector<vector<int>> adj(n + 1); for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
通过BFS构建树的父子关系:
queue<int> q; q.push(1); visited[1] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; parent[v] = u; children[u].push_back(v); // 建立子节点列表 q.push(v); } } }
2. 后序遍历标记子树
通过后序遍历标记每个节点的子树是否含核弹:
stack<pair<int, bool>> st; st.push({1, false}); while (!st.empty()) { auto [u, processed] = st.top(); st.pop(); if (!processed) { st.push({u, true}); // 逆序入栈以保证处理顺序 for (auto it = children[u].rbegin(); it != children[u].rend(); ++it) st.push({*it, false}); } else { for (int v : children[u]) { if (has_bomb[v]) { has_bomb[u] = true; // 子节点有核弹则标记 break; } } } }
例如,节点5的 has_bomb
为真,其父节点2的 has_bomb
也会被标记为真。
3. 统计控制器数量
遍历所有中转站节点,计算需要控制器数量:
int ans = 0; for (int u = 1; u <= n; ++u) { // 判断是否为中转站 bool is_station = (u == 1) || (!children[u].empty()); if (is_station) { int cnt = 0; for (int v : children[u]) { if (has_bomb[v]) cnt++; } ans += max(0, cnt - 1); // 关键计算 } }
-
根节点1:子节点2和4的子树含核弹 →
cnt=2
→ 贡献1
。 -
节点2:子节点5的子树含核弹 →
cnt=1
→ 贡献0
。 -
总控制器数为
1
。
邻接表与树构建示例
假设输入边为 1-2, 1-3, 1-4, 2-5
,邻接表如下:
1: [2,3,4] 2: [1,5] 3: [1] 4: [1] 5: [2]
通过BFS得到的父子关系:
1的子节点:2,3,4 2的子节点:5 3的子节点:无 4的子节点:无 5的子节点:无
总结
-
邻接表:存储图结构,每个节点维护相邻节点列表。
-
树构建:通过BFS确定父子关系,明确树形结构。
-
后序遍历:自底向上标记子树状态,确保父节点能继承子节点的核弹信息。
-
控制器计算:每个中转站需要覆盖的子节点数决定控制器数量。