2025年第十六届蓝桥杯大赛软件赛C/C++大学B组题解-试题G: 生产车间

时间：2025-05-14 19:42:09

问题描述

小明正在改造一个生产车间的生产流水线。这个车间共有n台设备，构成以1为根结点的一棵树，结点i有权值w_i。其中叶节点的权值w_i表示每单位时间将产出w_i单位的材料并送往父结点，根结点的权值w_i表示每单位时间内能打包多少单位成品，其他结点的权值w_i表示每单位时间最多能加工w_i单位的材料并送往父结点。

由于当前生产线中某些结点存在产能不够的问题导致生产线无法正常运行，即存在某些结点每单位时间收到的材料超过了当前结点的加工能力上限。小明计划删除一些结点使得所有结点都能正常运行。他想知道删除一些结点后根结点每单位时间内最多能打包多少单位的成品？

解题思路

这个问题描述了一个生产流水线优化场景：

  • 有n台设备构成一棵以1为根的树
  • 每个节点有权值w_i，表示其加工能力
  • 叶节点产生材料，非叶节点加工材料，根节点打包成品
  • 如果节点接收的材料超过其加工能力，生产线无法正常运行
  • 可以删除一些节点（及其子树）使所有节点正常运行
  • 目标是最大化根节点的产出

关键洞察：这是一个树形结构上的优化问题，我们需要决定保留或删除每个节点，以使根节点的产出最大化。要注意并不是每个节点的最大值组合起来并就一定是所求的最优解，比如样例数据，样例解释见代码后

我们采用自底向上的方法，从叶子节点开始，计算每个节点在不同情况下可能的产出值：

  1. 对于每个节点，我们有两个基本选择：

    • 保留节点：节点产生其权值的产出（对于叶子节点）或处理子节点的材料（对于非叶子节点）
    • 删除节点：节点产出为0

  2. 对于非叶子节点，我们需要：

    • 收集所有子节点的可能产出值
    • 组合这些产出值，确保总和不超过当前节点的加工能力
    • 计算当前节点所有可能的产出值

  3. 最终，根节点的最大可能产出值就是答案

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAX_NODES = 1005;
vector<int> g[MAX_NODES]; // 树结构的邻接表
int n, capacity[MAX_NODES]; // 节点数和各节点容量

/**
 * 计算以current_node为根的子树能提供的合法材料数值集合
 * @param current_node 当前处理的节点
 * @param parent_node 父节点（防止回溯）
 * @return 包含所有可能值的有序集合
 */
set<int> dfs(int current_node, int parent_node) {
	// g[current_node].size() == 1 表示无向图的叶子节点
	//parent_node != 0 避免出现链状
	if (g[current_node].size() == 1 && parent_node != 0) {
		return {capacity[current_node], 0}; // 保留或关闭该节点
	}
	
	set<int> valid_sums = {0}; // 初始化，包含0（全关闭情况）
	
	// 使用范围for循环遍历邻接节点
	for (int child_node : g[current_node]) {
		if (child_node == parent_node) continue; // 跳过父节点
		
		auto child_outputs = dfs(child_node, current_node);//深入遍历子节点
		set<int> current_sums = valid_sums; // 当前状态的副本
		
		//依次将任意两个子节点的所有取值进行组合
		for (int parent_sum : current_sums) {
			for (int child_contribution : child_outputs) {
				int total = parent_sum + child_contribution;
				if (total <= capacity[current_node]) {
					valid_sums.insert(total);
				}
			}
		}
	}
	return valid_sums;//返回该节点的所有取值情况
}

int main() {
	// 输入处理
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> capacity[i];
	}
	
	// 构建树结构
	for (int i = 1; i < n; ++i) {
		int node_a, node_b;
		cin >> node_a >> node_b;
		g[node_a].push_back(node_b);
		g[node_b].push_back(node_a);
	}
	
	// 计算并输出最大打包量
	cout << *dfs(1, 0).rbegin() << endl;
	
	return 0;
}

注意：这份代码在部分网站测试会有极少量测试集超时，对此可以使用使用位运算bitset代替集合：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXW = 1001;  // 最大权值+1

int n;                          // 节点数量
int w[MAXN];                    // 每个节点的权值（容量）
vector<int> graph[MAXN];        // 无向图邻接表

/**
 * 计算以u为根的子树能提供的合法材料数值集合
 * 使用bitset优化状态表示和组合操作
 * @param u 当前处理的节点
 * @param parent 父节点（防止回溯）
 * @return 包含所有可能值的位向量
 */
bitset<MAXW> dfs(int u, int parent) {
    // 判断是否为叶子节点
    if (graph[u].size() == 1 && parent != 0) {
        bitset<MAXW> result;
        result[0] = 1;          // 可以产出0（删除节点）
        result[w[u]] = 1;       // 可以产出w[u]（保留节点）
        return result;
    }
    
    // 初始化结果位向量，只有0位为1（表示所有子节点都关闭的情况）
    bitset<MAXW> result;
    result[0] = 1;
    
    // 遍历所有子节点
    for (int v : graph[u]) {
        if (v == parent) continue;  // 跳过父节点
        
        // 递归计算子节点的所有可能产出
        bitset<MAXW> child_outputs = dfs(v, u);
        
        // 保存当前结果的副本
        bitset<MAXW> current = result;
        result.reset();  // 清空结果
        
        // 优化的组合操作
        for (int i = 0; i <= w[u]; i++) {
            if (current[i]) {
                // 对于当前值i，与子节点的每个可能产出组合
                for (int j = 0; j <= w[u] - i; j++) {
                    if (child_outputs[j]) {
                        result[i + j] = 1;
                    }
                }
            }
        }
    }
    
    return result;  // 返回所有可能的产出值
}

int main() {
    ios_base::sync_with_stdio(false);  // 优化输入输出
    cin.tie(nullptr);
    
    cin >> n;
    
    // 读取每个节点的权值
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    
    // 读取树的边
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // 计算根节点的所有可能产出
    bitset<MAXW> root_outputs = dfs(1, 0);
    
    // 找出最大可能产出
    int ans = 0;
    for (int i = MAXW - 1; i >= 0; i--) {
        if (root_outputs[i]) {
            ans = i;
            break;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

样例详细阐述

让我们以给定的样例来详细说明算法的执行过程：

9
9 7 3 7 1 6 2 2 7
1 2
1 3
2 4
2 5
2 6
6 7
6 8
6 9

树的结构如下：

    1
   / \
  2   3
 /|\
4 5 6
   /|\
  7 8 9

节点权值：w = [9, 7, 3, 7, 1, 6, 2, 2, 7]（索引从1开始）

执行DFS过程：

  1. 叶子节点：

    • 节点3：返回3, 0
    • 节点4：返回7, 0
    • 节点5：返回1, 0
    • 节点7：返回2, 0
    • 节点8：返回2, 0
    • 节点9：返回7, 0

  2. 节点6（容量为6）：

    • 初始结果集：0

    • 处理子节点7（2, 0）：结果集变为0, 2

    • 处理子节点8（2, 0）：结果集变为0, 2, 4

    • 处理子节点9（7, 0）：

    • 0 + 0 = 0，已在结果集中

    • 0 + 7 = 7 > 6，超过容量，不添加

    • 2 + 0 = 2，已在结果集中

    • 2 + 7 = 9 > 6，超过容量，不添加

    • 4 + 0 = 4，添加到结果集

    • 4 + 7 = 11 > 6，超过容量，不添加

    最终结果集：0, 2, 4

  3. 节点2（容量为7）：

    • 初始结果集：0

    • 处理子节点4（7, 0）：结果集变为0, 7

    • 处理子节点5（1, 0）：结果集变为0, 1, 7, 8，但8 > 7，所以实际为0, 1, 7

    • 处理子节点6（0, 2, 4）：

    • 组合后得到0, 1, 2, 4, 7, 3 (2 + 1), 9 (2 + 7 应舍去), 5(4 + 1), 11(4 + 7 应舍去)

最终结果集：0, 1, 2, 3, 4, 5, 7

  1. 根节点1（容量为9）：

    • 初始结果集：0

    • 处理子节点2（0, 1, 2, 3, 4, 5, 7）：结果集变为0, 1, 2, 3, 4, 5, 7

    • 处理子节点3（3, 0）：

    • 组合后得到0, 1, 2, 3, 4, 5, 6 (3 + 3), 7 (4 + 3), 8 (5 + 3),10 (7 + 1)，但10 > 9，所以实际为0, 1, 2, 3, 4, 5, 6, 7, 8

最终结果集：0, 1, 2, 3, 4, 5, 6, 7, 8

  1. 最终答案：根节点1的结果集中的最大值为8

相关文章