当前位置: 首页 > article >正文

【蓝桥杯】雪地工程核弹引爆控制器最小数量计算

问题描述

危机纪元 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++1s256M
C1s256M
Java2s256M
Python33s256M
PyPy33s256M
Go3s256M
JavaScript3s256M

代码思路解析

  1. 输入处理与树构建
    通过邻接表存储树结构,并用BFS确定父子关系,构建每个节点的子节点列表。

  2. 核弹标记
    标记所有含有核弹的叶子节点。

  3. 后序遍历标记子树
    从叶子节点向上回溯,标记每个节点的子树是否包含核弹。若某节点的子节点子树包含核弹,则该节点也被标记。

  4. 统计控制器数量
    遍历每个信号中转站节点,统计其子节点中包含核弹的数目。若数目超过1,则需在该节点安装(数目-1)个控制器,确保信号正确传输。

关键点

  • 信号中转站判断:根节点或非叶子节点。

  • 后序遍历更新子树标记:确保父节点正确反映子树的核弹状态。

  • 控制器计算:每个中转站需要控制器数为其包含核弹子节点数减一,确保最少干预。

 

题目详细解析

我们用一个具体例子理解题目:

样例输入

5
1 2 
1 3
1 4
2 5
2 
4 5 

关键逻辑

  1. 信号传播规则

    • 中转站(非叶子非根节点)默认随机选择一个子节点。

    • 安装控制器后,中转站可以指定信号传递方向。

  2. 核心观察

    • 如果某个中转站的多个子节点的子树包含核弹,必须强制信号走向这些子节点。

    • 控制器的作用是减少选择的不确定性,确保覆盖所有核弹。

  3. 解决方案

    • 统计每个中转站节点需要引导的子节点数量。

    • 若某中转站有 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确定父子关系,明确树形结构。

  • 后序遍历:自底向上标记子树状态,确保父节点能继承子节点的核弹信息。

  • 控制器计算:每个中转站需要覆盖的子节点数决定控制器数量。

 

 


http://www.kler.cn/a/586611.html

相关文章:

  • Pytorch实现之最小二乘梯度归一化设计
  • 在离线情况下如何使用 Python 翻译文本
  • 【JVM】性能监控与调优概述篇
  • 基于RAGFlow本地部署DeepSpeek-R1大模型与知识库:从配置到应用的全流程解析
  • Spring Boot 中 BootstrapRegistryInitializer 的作用与示例
  • Ubuntu中为curl和Docker配置代理
  • Docker安装GitLab中文版详细流程,以及非80端口配置
  • 2025年渗透测试面试题总结-安恒 (题目+回答)
  • U盘提示格式化的深度解析与应对策略
  • 【新能源汽车研发测试能力建设深度解析:设备、趋势与行业展望】
  • 学习用WinDbg查看程序当前运行的堆栈
  • [C语言日寄] qsort函数的练习
  • css模拟雷达扫描动画
  • 用ST7789屏幕导致负片(反色)的问题
  • Alembic 实战指南:快速入门到FastAPI 集成
  • 深入解析对象存储及工作原理
  • Java 综合实战项目:生成不重复随机字符串数组
  • Android LeakCanary 使用 · 原理详解
  • 微信小程序面试内容整理-数据绑定
  • AcWing 4889. 空调II