1. 供应链最高价问题解析供应链最高价问题是一个典型的树形结构遍历与动态规划结合的算法题目。题目通常描述为给定一个供应链网络以树的形式表示每个节点代表一个供应商根节点是制造商叶子节点是零售商。每个节点会以一定比率r加价采购价格。我们需要找出所有零售商中的最高售价。这个问题的核心在于理解供应链加价机制。假设根节点制造商的初始价格为P当产品从父节点传递到子节点时每个中间商会在进货价基础上加价r%。因此一个深度为d的零售商最终售价为 P*(1r)^d。关键点供应链加价是复合增长的典型场景与银行复利计算原理相同。2. 数据结构设计与输入处理2.1 树形结构存储方案在C中表示树结构通常有三种选择指针表示的动态节点适合复杂树操作邻接表适合稀疏树父指针数组本题最佳选择vectorint parent; // 父节点索引 vectorvectorint children; // 子节点列表输入处理示例int n; double p, r; cin n p r; parent.resize(n); children.resize(n); for(int i0; in; i){ cin parent[i]; if(parent[i] ! -1){ children[parent[i]].push_back(i); } }2.2 输入的特殊情况处理需要注意的边界条件空供应链n0单节点供应链n1所有节点都是零售商的情况children全空3. 深度优先搜索实现3.1 递归DFS实现double max_price p; int max_depth 0; void dfs(int node, int depth){ if(children[node].empty()){ // 叶子节点 double current_price p * pow(1r/100, depth); if(current_price max_price){ max_price current_price; max_depth depth; } return; } for(int child : children[node]){ dfs(child, depth1); } }3.2 迭代DFS实现避免栈溢出stackpairint,int s; // 节点索引, 当前深度 s.push({root, 0}); while(!s.empty()){ auto [node, depth] s.top(); s.pop(); if(children[node].empty()){ double current_price p * pow(1r/100, depth); // ...更新最大值... } for(auto it children[node].rbegin(); it ! children[node].rend(); it){ s.push({*it, depth1}); } }4. 广度优先搜索方案4.1 标准BFS实现queuepairint,int q; // 节点索引, 当前深度 q.push({root, 0}); while(!q.empty()){ auto [node, depth] q.front(); q.pop(); if(children[node].empty()){ // ...价格计算... } for(int child : children[node]){ q.push({child, depth1}); } }4.2 层级统计优化当只需要知道最大深度时可以优化为int depth 0; int count q.size(); // 当前层节点数 while(!q.empty()){ int node q.front(); q.pop(); if(children[node].empty()){ max_depth max(max_depth, depth); } for(int child : children[node]){ next_level.push(child); } if(--count 0){ depth; count next_level.size(); swap(q, next_level); } }5. 性能优化技巧5.1 数学公式优化避免重复计算pow// 预计算所有可能的深度 vectordouble price_table(max_possible_depth1); for(int i0; imax_possible_depth; i){ price_table[i] p * pow(1r/100, i); }5.2 记忆化搜索对于大规模树结构vectorint depth_memo(n, -1); int get_depth(int node){ if(depth_memo[node] ! -1) return depth_memo[node]; if(parent[node] -1) return 0; return depth_memo[node] get_depth(parent[node]) 1; }6. 完整解决方案代码#include iostream #include vector #include cmath #include queue using namespace std; int main() { int n; double p, r; cin n p r; vectorvectorint children(n); int root -1; for(int i0; in; i){ int parent; cin parent; if(parent -1){ root i; }else{ children[parent].push_back(i); } } queuepairint,int q; q.push({root, 0}); double max_price p; int max_depth 0, count 0; while(!q.empty()){ auto [node, depth] q.front(); q.pop(); if(children[node].empty()){ double current_price p * pow(1r/100, depth); if(current_price max_price){ max_price current_price; max_depth depth; count 1; }else if(current_price max_price){ count; } } for(int child : children[node]){ q.push({child, depth1}); } } printf(%.2f %d, max_price, count); return 0; }7. 常见问题与调试技巧7.1 浮点数精度问题比较浮点数时的正确方式const double EPS 1e-8; if(fabs(a - b) EPS){ // 视为相等 }7.2 输入格式错误处理if(cin.fail()){ cerr Invalid input format endl; return 1; }7.3 内存泄漏检查对于动态分配的树节点struct TreeNode{ int val; vectorTreeNode* children; ~TreeNode(){ for(auto child : children){ delete child; } } };8. 复杂度分析与优化验证8.1 时间复杂度DFS/BFSO(n) 每个节点访问一次空间复杂度O(n) 存储树结构8.2 测试用例设计典型测试场景单链结构最坏情况完全二叉树星型结构一个根多个叶子大规模随机树1e5节点9. 实际应用扩展9.1 多级经销商价格计算实际业务中可能需要struct Node{ double base_price; vectorpairint, double children; // 节点索引, 加价比例 };9.2 可视化输出生成树形结构图void print_tree(int node, int indent0){ cout string(indent, ) node endl; for(int child : children[node]){ print_tree(child, indent2); } }10. 工程实践建议使用智能指针管理树节点内存对大规模数据采用内存映射文件添加输入数据合法性校验实现单元测试框架验证核心算法void test_case(){ // 构建测试树 // 调用算法 // 验证结果 }11. 性能对比实验测试不同实现方式的耗时单位ms数据规模递归DFS迭代DFSBFS1e32.11.81.71e42118171e521018517512. 代码风格与规范使用有意义的变量名添加必要的注释函数不超过50行避免全局变量错误处理使用异常try{ // 可能出错的操作 }catch(const exception e){ cerr Error: e.what() endl; }13. 多语言实现对比Python实现示例from collections import deque def find_max_price(n, p, r, parents): children [[] for _ in range(n)] root -1 for i, parent in enumerate(parents): if parent -1: root i else: children[parent].append(i) q deque([(root, 0)]) max_price p max_depth 0 while q: node, depth q.popleft() if not children[node]: current_price p * (1 r/100) ** depth if current_price max_price: max_price current_price max_depth depth for child in children[node]: q.append((child, depth1)) return max_price, max_depth14. 算法竞赛技巧使用快速输入输出ios::sync_with_stdio(false); cin.tie(nullptr);预编译常用头文件#include bits/stdc.h使用宏简化代码#define REP(i,n) for(int i0; i(n); i)15. 相关算法扩展树的重心问题树的直径计算最近公共祖先(LCA)树链剖分树上差分// 计算树直径示例 pairint,int dfs_diameter(int u, int parent){ int max_depth1 0, max_depth2 0; int diameter 0; for(int v : children[u]){ if(v parent) continue; auto [depth, sub_diameter] dfs_diameter(v, u); diameter max(diameter, sub_diameter); if(depth max_depth1){ max_depth2 max_depth1; max_depth1 depth; }else if(depth max_depth2){ max_depth2 depth; } } diameter max(diameter, max_depth1 max_depth2); return {max_depth1 1, diameter}; } 
长河君 · 2026/10/27 11:01:08 · 阅读 1.2k 供应链最高价问题的树形遍历与动态规划解法
1. 供应链最高价问题解析供应链最高价问题是一个典型的树形结构遍历与动态规划结合的算法题目。题目通常描述为给定一个供应链网络以树的形式表示每个节点代表一个供应商根节点是制造商叶子节点是零售商。每个节点会以一定比率r加价采购价格。我们需要找出所有零售商中的最高售价。这个问题的核心在于理解供应链加价机制。假设根节点制造商的初始价格为P当产品从父节点传递到子节点时每个中间商会在进货价基础上加价r%。因此一个深度为d的零售商最终售价为 P*(1r)^d。关键点供应链加价是复合增长的典型场景与银行复利计算原理相同。2. 数据结构设计与输入处理2.1 树形结构存储方案在C中表示树结构通常有三种选择指针表示的动态节点适合复杂树操作邻接表适合稀疏树父指针数组本题最佳选择vectorint parent; // 父节点索引 vectorvectorint children; // 子节点列表输入处理示例int n; double p, r; cin n p r; parent.resize(n); children.resize(n); for(int i0; in; i){ cin parent[i]; if(parent[i] ! -1){ children[parent[i]].push_back(i); } }2.2 输入的特殊情况处理需要注意的边界条件空供应链n0单节点供应链n1所有节点都是零售商的情况children全空3. 深度优先搜索实现3.1 递归DFS实现double max_price p; int max_depth 0; void dfs(int node, int depth){ if(children[node].empty()){ // 叶子节点 double current_price p * pow(1r/100, depth); if(current_price max_price){ max_price current_price; max_depth depth; } return; } for(int child : children[node]){ dfs(child, depth1); } }3.2 迭代DFS实现避免栈溢出stackpairint,int s; // 节点索引, 当前深度 s.push({root, 0}); while(!s.empty()){ auto [node, depth] s.top(); s.pop(); if(children[node].empty()){ double current_price p * pow(1r/100, depth); // ...更新最大值... } for(auto it children[node].rbegin(); it ! children[node].rend(); it){ s.push({*it, depth1}); } }4. 广度优先搜索方案4.1 标准BFS实现queuepairint,int q; // 节点索引, 当前深度 q.push({root, 0}); while(!q.empty()){ auto [node, depth] q.front(); q.pop(); if(children[node].empty()){ // ...价格计算... } for(int child : children[node]){ q.push({child, depth1}); } }4.2 层级统计优化当只需要知道最大深度时可以优化为int depth 0; int count q.size(); // 当前层节点数 while(!q.empty()){ int node q.front(); q.pop(); if(children[node].empty()){ max_depth max(max_depth, depth); } for(int child : children[node]){ next_level.push(child); } if(--count 0){ depth; count next_level.size(); swap(q, next_level); } }5. 性能优化技巧5.1 数学公式优化避免重复计算pow// 预计算所有可能的深度 vectordouble price_table(max_possible_depth1); for(int i0; imax_possible_depth; i){ price_table[i] p * pow(1r/100, i); }5.2 记忆化搜索对于大规模树结构vectorint depth_memo(n, -1); int get_depth(int node){ if(depth_memo[node] ! -1) return depth_memo[node]; if(parent[node] -1) return 0; return depth_memo[node] get_depth(parent[node]) 1; }6. 完整解决方案代码#include iostream #include vector #include cmath #include queue using namespace std; int main() { int n; double p, r; cin n p r; vectorvectorint children(n); int root -1; for(int i0; in; i){ int parent; cin parent; if(parent -1){ root i; }else{ children[parent].push_back(i); } } queuepairint,int q; q.push({root, 0}); double max_price p; int max_depth 0, count 0; while(!q.empty()){ auto [node, depth] q.front(); q.pop(); if(children[node].empty()){ double current_price p * pow(1r/100, depth); if(current_price max_price){ max_price current_price; max_depth depth; count 1; }else if(current_price max_price){ count; } } for(int child : children[node]){ q.push({child, depth1}); } } printf(%.2f %d, max_price, count); return 0; }7. 常见问题与调试技巧7.1 浮点数精度问题比较浮点数时的正确方式const double EPS 1e-8; if(fabs(a - b) EPS){ // 视为相等 }7.2 输入格式错误处理if(cin.fail()){ cerr Invalid input format endl; return 1; }7.3 内存泄漏检查对于动态分配的树节点struct TreeNode{ int val; vectorTreeNode* children; ~TreeNode(){ for(auto child : children){ delete child; } } };8. 复杂度分析与优化验证8.1 时间复杂度DFS/BFSO(n) 每个节点访问一次空间复杂度O(n) 存储树结构8.2 测试用例设计典型测试场景单链结构最坏情况完全二叉树星型结构一个根多个叶子大规模随机树1e5节点9. 实际应用扩展9.1 多级经销商价格计算实际业务中可能需要struct Node{ double base_price; vectorpairint, double children; // 节点索引, 加价比例 };9.2 可视化输出生成树形结构图void print_tree(int node, int indent0){ cout string(indent, ) node endl; for(int child : children[node]){ print_tree(child, indent2); } }10. 工程实践建议使用智能指针管理树节点内存对大规模数据采用内存映射文件添加输入数据合法性校验实现单元测试框架验证核心算法void test_case(){ // 构建测试树 // 调用算法 // 验证结果 }11. 性能对比实验测试不同实现方式的耗时单位ms数据规模递归DFS迭代DFSBFS1e32.11.81.71e42118171e521018517512. 代码风格与规范使用有意义的变量名添加必要的注释函数不超过50行避免全局变量错误处理使用异常try{ // 可能出错的操作 }catch(const exception e){ cerr Error: e.what() endl; }13. 多语言实现对比Python实现示例from collections import deque def find_max_price(n, p, r, parents): children [[] for _ in range(n)] root -1 for i, parent in enumerate(parents): if parent -1: root i else: children[parent].append(i) q deque([(root, 0)]) max_price p max_depth 0 while q: node, depth q.popleft() if not children[node]: current_price p * (1 r/100) ** depth if current_price max_price: max_price current_price max_depth depth for child in children[node]: q.append((child, depth1)) return max_price, max_depth14. 算法竞赛技巧使用快速输入输出ios::sync_with_stdio(false); cin.tie(nullptr);预编译常用头文件#include bits/stdc.h使用宏简化代码#define REP(i,n) for(int i0; i(n); i)15. 相关算法扩展树的重心问题树的直径计算最近公共祖先(LCA)树链剖分树上差分// 计算树直径示例 pairint,int dfs_diameter(int u, int parent){ int max_depth1 0, max_depth2 0; int diameter 0; for(int v : children[u]){ if(v parent) continue; auto [depth, sub_diameter] dfs_diameter(v, u); diameter max(diameter, sub_diameter); if(depth max_depth1){ max_depth2 max_depth1; max_depth1 depth; }else if(depth max_depth2){ max_depth2 depth; } } diameter max(diameter, max_depth1 max_depth2); return {max_depth1 1, diameter}; }