树形贪心算法求解网络放大器设置问题：C++实现与避坑指南

简介针对山东大学数据结构与算法课程设计中的网络放大器设置问题资源以加权有向无环图为背景演示如何用最少压力放大器保证汽油输送压力不低于Pmin。压缩包共9个文件主要包含cpp源码、txt测试样例与运行时间记录、md说明文档整体仅4KB结构紧凑附有详细注释、多组样例及算法性能对比图表。内容覆盖BFS与DFS两种解法BFS时间复杂度O(n²)DFS即便加入剪枝仍需遍历大量可能解、时间复杂度接近O(2^n)并通过实测时间数据清晰展示差异有助于理解不同策略在图优化问题中的表现。已有262人学习/下载适合正在完成山东大学该课程设计或需要参考网络放大器求解思路的学生使用。读者可直接参考源码与注释利用测试样例验证结果结合图表完成实验报告中的性能比较分析。1. 网络放大器设置问题一个树形贪心算法的最小放置数难题先说一个反直觉的结论在一棵信号衰减树上放置放大器最优位置往往不在叶子附近也不在根上而是在信号刚好“还能撑住”的那一层节点上。这个项目就是某高校数据结构与算法课程设计里的网络放大器设置问题核心是用 C 实现一个基于树形结构的贪心算法在给定每条边的传输损耗和一根衰减阈值后算出最少需要放置多少台放大器、分别放在哪些节点并配了详细注释、多组测试样例和拓扑图表。对正在做课程设计、或者想练树与贪心算法的人来说这是一份能直接跑、能照着改的完整工程对想复习回溯遍历的开发者它也是一份浓缩的算法实战样例。2. 问题建模与资源结构把传输网络抽象成一棵带权树2.1 从实际问题到图论模型通信网络里有一个常见场景信号从根节点出发沿着树形拓扑向下传输每经过一条边就会损耗掉一部分强度。如果损耗太大叶子节点收到的信号就会低于设备要求的最低阈值。解决思路是在某些节点放置网络放大器让信号在该节点被恢复到初始强度再继续向下传输。问题变成选择哪些节点放置放大器既能保证所有叶子节点最终收到的信号不低又让放大器的数量最少。这个场景天然适合用带权树来建模。树根是信号源边权是一条链路的传输损耗叶子是信号的最终接收端。项目里把阈值记为T含义是“任意一段连续传输中累积损耗不能超过 T”。注意这里的“连续传输”指的是从某个放大器或树根出发到它覆盖到的某个叶子节点之间的路径损耗。也就是说每个放大器都是一段传输的新起点它把信号拉满重新开始累计损耗。理解了这层含义贪心策略就顺理成章了从叶子往根回溯一旦发现某个节点到它某个后代叶子之间的最大累积损耗已经达到或超过阈值 T就在这个节点放置放大器。这样每个放大器能覆盖尽量大的一片子树同时保证任意叶子到它最近的上游放大器之间的损耗不会超限。2.2 项目目录结构与文件角色资源解压后是一个标准的课程设计工程结构目录不算复杂但每个文件承担的职责很明确。network-amplifier/ ├── README.md # 问题描述、设计思路、运行说明 ├── src/ │ └── main.cpp # 核心算法与输入输出实现 ├── test/ │ ├── case1.in # 小型树4 个叶子验证基本放置 │ ├── case2.in # 中型树7 个节点含边界阈值 │ ├── case3.in # 深度链式树验证链路累计衰减 │ └── case1.out # 对应输出与期待结果 └── doc/ ├── 网络拓扑结构图.png # 原始树形网络标图 ├── 放大器放置策略图.png # 标出放大器位置的结果图 └── 设计文档.md # 算法证明、复杂度分析、测试说明我第一次拿到这套代码时先看的是README.md里给的输入格式第一行是两个整数n Tn表示节点数量节点编号从 1 到 nT是衰减阈值接下来n-1行每行三个整数u v w表示节点 u 和节点 v 之间有一条衰减量为 w 的双向边。输出格式是两行第一行是放大器数量第二行是放置放大器的节点编号。这种格式很适合做自动化测试。我一般会写一个循环脚本批量跑test目录下的所有用例把输出和.out文件逐行对比。项目里test/case2.in设计得很用心它把阈值恰好卡在某个节点到叶子的累计损耗上专门用来检验边界条件和的区别这一点在后面的避坑章节会重点展开。2.3 图表资源怎么读文档目录里的两张图一张是原始网络拓扑图一张是放置放大器后的结果图。原始图上每条边标注了损耗值叶子节点用空心圆表示结果图里被选为放大器的节点用实心圆标出并且从该节点向下的子树用不同颜色的虚线框起来表示这段传输从放大器开始重新计损。看这两张图时建议先自己手写一遍贪心过程再和图上标出的放置位置对比。我第一次读放大器放置策略图时发现放置点都不是叶子而是分支节点这个直觉很关键贪心算法倾向于在“信号即将耗尽”的那个较高层节点放放大器这样一台放大器能覆盖更多叶子数量自然更少。3. 核心算法拆解DFS 回溯与阈值判断的完整链路3.1 数据结构定义与邻接表建树代码用邻接表存树每条边用一个结构体记录目标节点和损耗值。这种写法在竞赛和课程设计里都很常见比二维数组省空间对稀疏树也更友好。#include bits/stdc.h using namespace std; const int MAXN 1005; struct Edge { int to; // 目标节点编号 int w; // 这条边的传输损耗 }; vectorEdge tree[MAXN]; // 邻接表tree[u] 存从 u 出发的所有边 int T; // 全局阈值允许的最大累计损耗 vectorint ans; // 放置放大器的节点列表这里把T和ans设为全局变量是为了在递归函数里少传参数让 DFS 逻辑更清晰。MAXN取 1005 是给上限 1000 个节点的测试数据留余量。建树的时候别忘了是无向边每条边要往两个节点的邻接表里各压一次否则 DFS 从根出发会走不到某些节点。3.2 DFS 回溯返回子树最大累计损耗核心函数是dfs它接收当前节点u和父节点parent返回从u出发、到它子树中某个叶子的最大累积损耗。这个返回值是判断是否放置放大器的依据。// 返回从 u 到其子树叶子方向上的最大累计损耗 int dfs(int u, int parent) { int maxLoss 0; // 当前节点到子树叶子方向的最大累计损耗 for (const Edge e : tree[u]) { if (e.to parent) continue; // 跳过父节点避免往回走 // 子节点的最大损耗 当前边的损耗就是经过这条分支的累计损耗 int loss dfs(e.to, u) e.w; maxLoss max(maxLoss, loss); } // 如果从当前节点出发到某个叶子的累计损耗达到阈值 // 说明再往上走信号就撑不住了必须在当前节点放置放大器 if (maxLoss T) { ans.push_back(u); // 记录放置点 return 0; // 信号在当前节点被放大器恢复累计损耗归零 } return maxLoss; // 未超限把累计损耗继续向上传递 }这段代码是整个项目的灵魂。简单说一下逻辑链从根节点调用dfs(1, 0)递归到叶子节点时叶子没有子分支maxLoss是 0直接返回 0。回到上层节点后把每条子分支返回的损耗加上当前边的w取最大值作为当前节点的maxLoss。如果maxLoss T说明从当前节点往下走存在一条路径的损耗会超过或等于阈值于是把当前节点记录为放大器并返回 0。返回 0 这一行很关键。它表示这条子树方向上的信号已经被当前节点的放大器“刷新”了父节点在计算路径损耗时不需要再累加这棵子树内部的损耗只需要计算从父节点到当前节点的边损耗即可。参数说明u是当前遍历到的节点编号parent是它的父节点编号用来在无向图中避免递归回退到父节点形成死循环。这种方式比单独维护一个visited数组更轻量是树形 DFS 的惯用写法。3.3 主函数与输入输出处理主函数的职责是读数据、建树、调用 DFS、输出结果。项目注释里特意提醒了根节点编号固定为 1输入不要出现 0 号节点。int main() { int n; cin n T; for (int i 1; i n; i) { int u, v, w; cin u v w; tree[u].push_back({v, w}); tree[v].push_back({u, w}); } dfs(1, 0); sort(ans.begin(), ans.end()); // 输出前排序保证编号从小到大 cout ans.size() \n; for (int v : ans) { cout v ; } cout \n; return 0; }这里有个输出细节DFS 的回溯顺序是后进先出ans里记录节点的顺序是遍历访问到的先后顺序不是编号顺序。课程设计要求输出稳定的测试结果所以最后必须排序。我刚开始跑测试的时候就因为没排序导致和.out文件对不上白白排查了半天。n的读入是边数加一因为树有 n 个节点、n-1 条边。如果你拿到的测试数据第一行是节点数和边数两个值那读入逻辑要相应调整这个兼容性问题在避坑章节会提到。3.4 复杂度与正确性直觉每个节点在执行dfs时只检查了自己的所有邻边而树的总边数是 n-1所以整体时间复杂度是 O(n)空间复杂度是 O(n)邻接表存储加递归栈深度。对课程设计的数据规模来说完全足够。正确性的直觉可以这样理解如果某个节点到它某个叶子之间的最大损耗已经超过阈值那么在这个节点以下的任何位置放置放大器只能覆盖那一条分支覆盖不了同一节点的其他分支如果放在当前节点则所有子分支都能被这同一个放大器覆盖。贪心选择当前节点既满足约束又让放大器数量不会比任何最优解多。这个贪心在“每条边损耗非负、放大器恢复量恒定”的前提下是成立的。4. 测试样例与避坑指南跑通样例只是开始边界情况才是翻车高发区4.1 手写第一个样例验证思路我第一次跑通代码之后没有急着换大数据而是手搓了一棵 7 节点的小树来验证逻辑样例长这样7 6 1 2 3 2 4 5 2 5 4 1 3 2 3 6 3 3 7 6这棵树里根节点 1 有两个子树节点 2 下方连着叶子 4边损耗 5和叶子 5边损耗 4节点 3 下方连着叶子 6边损耗 3和叶子 7边损耗 6。阈值 T 设为 6。手动跑一遍 DFS叶子 4 返回 0节点 2 那边 maxLoss 5 3 88 6所以节点 2 放置放大器并返回 0节点 3 那边 maxLoss 是 6刚好等于阈值6 6 成立节点 3 也放置放大器并返回 0根节点 1 的 maxLoss 2 0 2不超。输出两个节点 2 和 3。这个样例的价值在于把和的差别直接暴露出来。如果把判断写成maxLoss T节点 3 的 6 不大于 6不会放放大器那么叶子 7 到最近放大器节点 1的累计损耗是 2 6 8超过阈值方案就挂掉了。凡是看到阈值刚好卡在某个叶子累计损耗上的用例都要警觉。4.2 避坑一边界条件用 还是 结果天差地别现象样例 2 跑出来放大器数量比答案少一个叶子节点信号强度不达标。原因判断条件写成了maxLoss T把“损耗恰好等于阈值”的场景漏掉放大器少放了一个。解决统一改用maxLoss T并专门构造一个“损耗恰好等于阈值”的用例来回归验证。这个边界是我在这类题目里踩过最多次的坑没有之一。4.3 避坑二递归深度过大导致栈溢出现象测试数据是一棵深度 10000 的链式树程序运行到一半直接崩溃报栈溢出。原因递归实现依赖系统调用栈默认栈空间有限链式树的递归深度等于节点数很容易爆栈。解决课程设计范围内可以直接把递归改成显式栈迭代用stackpairint,int模拟 DFS 回退或者在一些在线评测环境里用编译器选项扩大栈空间。我给项目扩展迭代版时额外维护了一个status数组记录每个节点是否已处理完子分支才把这个问题彻底绕开。4.4 避坑三无向图建树时漏掉反向边现象输入样例后程序只访问了部分节点放大器数量明显偏少。原因建树时只把边压入一个方向的邻接表DFS 顺着单向边走不到另一半节点。解决每条边必须push_back两次同时用parent参数防止递归回退。这个坑看起来很基础但在我第一次自己动手实现时依然翻车了因为样例数据恰好是从根按顺序给的掩盖了问题。4.5 避坑四根节点固定为 1但输入不按根顺序给现象换成另一组测试数据后输出完全错乱放置点出现在不合理的节点上。原因项目约定节点 1 是信号源但输入体顶部的边并非按从根到叶子的顺序排列如果先入为主地认为第一次出现的节点是根就会把父亲关系搞错。解决严格遵守约定DFS 从节点 1 开始parent参数只用于避免回退不依赖输入顺序。更稳妥的做法是在读入时额外指定一个root变量方便适配不同数据。4.6 避坑五输出放大器编号顺序不稳定现象多次运行同一份数据放大器数量相同但编号输出顺序不一样。原因ans的记录顺序由 DFS 访问顺序决定而访问顺序和图邻接表的插入顺序相关不同编译器或不同输入顺序都会影响结果。解决输出前统一sort。这也是课程设计评分里容易被忽略的一环测试脚本比对输出都是逐字符匹配排序能保证结果稳定可复现。5. 二次开发技巧把固定解法扩展成可配置、可扩展的放大器决策工具这套代码的扩展空间其实不小。第一个值得改的方向是“带权放置成本”现实里在不同节点部署放大器的成本可能不同比如设备费用、施工难度各有差异。原来的贪心只保证数量最少不保证总成本最低。这种情况可以把问题升级成树形 DP状态定义为dp[u][k]表示以 u 为根的子树上、离 u 最近的放大器距离为 k 时的最小成本转移时枚举每条子分支的状态思路和经典的最小顶点覆盖类似。第二个方向是支持自定义参数。我一般会在main里加一个配置文件读取逻辑格式可以很简单root1 threshold6 amplifier_costuniform用ifstream读进来后把阈值和根节点存成变量这样不用重新编译就能跑不同的网络拓扑。如果想让输出更直观还可以加一个--export参数把结果导出成 Graphviz 的 DOT 格式配合可视化工具直接生成标好放大器位置的树图课程设计答辩时会比贴一张静态图更有说服力。第三个更实用的改造是把单组测试改成多组批量测试。在main最外层套一个while (cin n T)每组数据内部先把tree的vector清空再重新建树。我在给这个项目做扩展时顺手写了一个 Python 脚本随机生成树形数据每次把输出文件拿到diff里和原版程序的结果对比验证改造后是否保持了相同行为。从那以后我每次拿到一棵新的树都会先手写一颗只有五六节点的样例把阈值分别设成恰好等于某条路径损耗、小于最小边损耗、大于整棵树最大路径损耗这三种情况强制自己完整跑一遍调试流程再上大数据。这套习惯帮我挡掉了好几次在边界条件上翻车的尴尬。希望这些拆解过程能帮你在做类似课程设计时少走几步弯路也祝你一次跑通。本文还有配套的精品资源点击获取