简介山东大学数据结构与算法课程设计实验四“网络放大器设置问题”的完整实现包面向高校数据结构与算法课程学习者及需要完成相似图论实验的同学。资源基于加权有向无环图建模汽油传送网络围绕最小压力Pmin与最大压力Pmax的约束求解放置放大器的最少数量。包内共9个文件含2个C源文件实验主程序与时间性能测试、6个txt文本多组测试样例及两种方案的运行时间记录和1个md说明文档整体仅4KB便于快速下载查阅。已有262人学习使用。代码附带详细注释并分别采用BFSO(n²)与DFSO(2^n)求解通过图表对比两种方法的时间性能同时讨论贪心算法的局部最优策略。读者可直接运行验证也能从中学习图算法设计、复杂度分析与实验报告整理思路。1. 网络放大器设置问题从课程设计题目到一棵树的动态规划很多高校的数据结构课程设计里都有一道叫网络放大器设置问题的题信号从根节点发出沿树形网络逐级衰减每个节点又有自己最低的信号门槛问最少在哪些节点安装放大器才能让整棵树上的节点都收到足够强的信号。第一眼看到这道题大多数人会试图直接模拟信号传播走一个节点算一次边走边放放大器结果要么多放、要么漏放。其实这道题的本质是树形动态规划先用一次后序遍历算出每个子树至少需要多少“进场信号”再自顶向下判断应该在哪放。整套方案适合正在做课程设计的同学也适合想把自己的题解整理成完整文档的开发者。下面从建模讲到验收答辩代码可以直接照搬。2. 总体设计数据结构选型与两条设计路径2.1 问题建模把网络看成带损耗的树网络放大器设置问题可以形式化成一个带权有向树模型。假设信号源放在树的根节点编号为 0。树上每一条边对应一段通信链路链路上有一个损耗值 loss信号经过这条边会减少 loss。每个节点 i 有一个接收阈值 threshold[i]意思是该节点要正常工作收到的信号强度必须不低于这个值。初始信号强度 MAX_SIGNAL 是固定的如果某个节点放置了放大器那么从这个节点再往下发信号时信号会被重置成 MAX_SIGNAL。目标是在满足所有节点接收信号达标的条件下最小化放大器的数量。这里注意一点放大器只能放在节点上不能放在链路中间根节点作为信号源通常不需要再放放大器因为放大器只是把信号恢复成初始强度对根节点没有意义。为什么必须把网络抽象成树而不是通用的图因为信号的方向是单向的从根向外扩散不会出现环回路径。把输入构造为“父节点 - 子节点”的有向边就能直接用树的遍历处理。输入数据里往往只给 n、边三元组 (u, v, loss) 以及每个节点的阈值 threshold[i]并不保证边的输入顺序就是树的拓扑顺序所以建立邻接表之后要先用一次遍历确定父子关系这个细节在后面的避坑部分会专门展开。2.2 数据结构选型邻接表存储树用 C 实现时我一般选择 vectorEdge 数组来存子节点而不是邻接矩阵。原因有两个一是树是稀疏图n 个节点只有 n-1 条边用 n 乘 n 的邻接矩阵浪费空间节点数量上万时内存直接爆掉二是后序和先序两次遍历都需要频繁访问某个节点的所有子节点邻接表刚好能做到高效枚举。const int MAXN 10005; struct Edge { int to; // 子节点编号 int loss; // 这条链路上的信号损耗 }; vectorEdge children[MAXN]; // children[u] 存放 u 的所有子节点 int thresholdVal[MAXN]; // 每个节点的接收阈值这里把每条边存成“父节点 - 子节点”的方向。如果原始输入是无向边需要先做一次从根开始的 BFS 或 DFS把边定向再填入 children。节点编号从 0 开始根节点固定为 0整个数据结构非常简单却刚好支撑起后续两次遍历。除了邻接表还需要一个数组 need[u]表示“以 u 为根的子树要让整棵子树内所有节点都达标进入 u 节点时的信号至少需要多少”。这个数组是算法的核心与 children、thresholdVal 一起构成全部状态。换句话说模型里真正参与计算的只有三类数据树的结构、节点的门槛、子树的综合需求。2.3 路线对比自顶向下模拟 vs 自底向上算需求最直接的想法是从根带一个信号往下走走到某个节点如果当前信号低于该节点的阈值就在这个节点放一个放大器把信号恢复满然后继续往下走。这个做法看起来是对的实际一跑就会翻车。原因在于当前节点信号不够不代表问题出在当前节点可能是它的子节点需求太高需要在更深的位置解决也可能当前节点只是阈值略有不足而它的兄弟分支根本没有压力如果在这里放大会产生冗余。所以单纯自顶向下模拟拿不到最优解。正确做法是分两步先自底向上算出 need[u]再自顶向下携带实际信号做放置决策。两条路线的对比如下。维度自顶向下模拟需求计算 放置决策遍历次数一次边遍历边决策两次后序 先序需要的信息只看当前节点阈值需要整棵子树的最高需求能否保证最少放大器不能容易多放能需求覆盖完整实现复杂度简单但错误率高代码略长但结果稳定第二步带着实际信号走只有当实际信号低于 need[u] 时才在这个节点放放大器。因为 need[u] 已经考虑了整棵子树的所有阈值和链路损耗所以在该节点放大之后一定可以覆盖它的所有后代不会出现“放了放大器下层还是不够”的情况。两步遍历的复杂度都是 O(n)相加之后整体仍然是 O(n)对课程设计输入规模来说完全够用。2.4 整体流程四个模块的职责划分整套程序按四个模块拆开每个模块的职责可以单独测试。输入模块读入 n、阈值数组、m 条边三元组建立 children 邻接表。需求计算模块调用 dfsNeed 做后序遍历计算每个节点的 need[u]。放置决策模块调用 dfsPlace 做先序遍历携带实际信号判断是否需要放放大器。结果输出模块打印放大器数量、放置节点列表以及每个节点最终接收到的信号强度表。调用顺序只有一种先 dfsNeed 计算出需求再 dfsPlace 做决策。如果把顺序颠倒dfsPlace 在判断“信号不够”时缺少整棵子树的全局信息又回到自顶向下模拟的错误路径。这里我习惯在代码注释里加一行“先算需求再定放置顺序不能变”因为真的很容易在调试时把两个调用写反。用一张树形结构图描述后面要验证的样例网络先看拓扑输入数据在测试章节统一给出0(信号源) / \ (5) (8) 1 2 / \ \ (6) (4) (3) 3 4 5图中节点编号旁边的数字是链路的损耗值括号内是边上的信号衰减量。这张图对应一个真实的输入文件后面第 5 章会对它做完整计算和验收。3. 核心实现C 版本的需求计算与放大器放置3.1 数据结构定义与输入读取把数据结构和常量放在一起方便后续调整 MAX_SIGNAL 的大小。输入文件第一行是节点数 n第二行是 n 个阈值第三行是边数 m之后 m 行每行是一条边“父节点 子节点 损耗”。课程设计要求里有详细注释所以下面代码里关键行都写了说明。#include bits/stdc.h using namespace std; const int MAXN 10005; const int MAX_SIGNAL 30; // 信号源强度和放大器恢复值 struct Edge { int to; // 子节点编号 int loss; // 链路损耗 }; vectorEdge children[MAXN]; int thresholdVal[MAXN]; // 节点接收阈值 int need[MAXN]; // 子树最低进场需求 int answer 0; vectorint placedNodes; // 放置放大器的节点集合 int main() { freopen(amplifier.in, r, stdin); freopen(amplifier.out, w, stdout); int n; cin n; for (int i 0; i n; i) { cin thresholdVal[i]; } int edgeCount; cin edgeCount; for (int i 0; i edgeCount; i) { int u, v, loss; cin u v loss; children[u].push_back({v, loss}); } return 0; }这里要求输入已经按照“父节点在前、子节点在后”的格式给出。如果题目给的是无向边需要先做一次定向具体处理方式放在第 4 章。MAX_SIGNAL 的值是全局共享的放大器和信号源共用同一个恢复强度这个值要和阈值、损耗的数据范围一起读题确认。3.2 自底向上的需求计算 dfsNeeddfsNeed 用后序遍历实现先递归处理所有子节点再回到当前节点汇总需求。某个子节点 v 的需求是 need[v]从 u 进入 v 要经过一条损耗为 loss 的边所以从 u 出发时至少要有 need[v] loss 的信号强度。多个子节点之间取最大值再和当前节点自己的阈值比一比。void dfsNeed(int u) { need[u] thresholdVal[u]; // 先把自己这一关算进去 for (const Edge e : children[u]) { dfsNeed(e.to); need[u] max(need[u], need[e.to] e.loss); } }这个函数的核心思想是need[u] 代表进入 u 的最低信号强度只要能满足 need[u]u 的所有后代都能正常工作。取 max 是因为父节点发出的信号是同一个强度所有子节点分支共享这个信号最吃紧的那个分支决定了整体需求。叶子节点没有子节点所以 need 直接等于自身阈值。参数说明u 是当前节点编号函数没有返回值结果写进全局数组 need。后序遍历的顺序保证子节点的 need 一定先算完父节点汇总时数据是完整的。这段代码看似只有几行但整个算法的最优性都靠它撑着。3.3 自顶向下的放置决策 dfsPlacedfsPlace 携带一个 currentSignal 参数表示进入当前节点的实际信号强度。判断条件只有一句如果这个信号小于 need[u]就在 u 放放大器然后把 currentSignal 重置为 MAX_SIGNAL。void dfsPlace(int u, int currentSignal) { // 根节点是信号源不在根上放放大器 if (u ! 0 currentSignal need[u]) { answer; placedNodes.push_back(u); currentSignal MAX_SIGNAL; } // 信号经过链路损耗后传给子节点 for (const Edge e : children[u]) { dfsPlace(e.to, currentSignal - e.loss); } }正确性的关键在于当前信号小于 need[u] 时无论如何这条子树都需要一个放大器来“兜底”而放在 u 是覆盖范围最小、最节省的选择。放在 u 的父节点虽然也能恢复信号但父节点可能同时分管好几条分支放大器放得越靠上越可能因为某个分支而拖累整个决策也更容易出现冗余放置。参数说明u 是当前节点currentSignal 是实际进入 u 的信号强度。递归进入子节点时信号要减去链路损耗如果减成负数也不用担心子节点进入时会拿这个负数去和 need 比较必然触发放置逻辑。调用时从根开始dfsPlace(0, MAX_SIGNAL)。3.4 主函数与输出模块主函数先调用 dfsNeed 再调用 dfsPlace最后输出答案数量、放置节点列表以及每个节点最终的信号强度。输出信号强度表不是题目必需的但课程设计报告里放一张表比只给一个答案数字有说服力得多也方便和测试样例做比对。void dfsReport(int u, int currentSignal) { if (u ! 0 currentSignal need[u]) { currentSignal MAX_SIGNAL; } cout 节点 u 信号强度: currentSignal \n; for (const Edge e : children[u]) { dfsReport(e.to, currentSignal - e.loss); } } int main() { freopen(amplifier.in, r, stdin); freopen(amplifier.out, w, stdout); int n; cin n; for (int i 0; i n; i) { cin thresholdVal[i]; } int edgeCount; cin edgeCount; for (int i 0; i edgeCount; i) { int u, v, loss; cin u v loss; children[u].push_back({v, loss}); } dfsNeed(0); dfsPlace(0, MAX_SIGNAL); dfsReport(0, MAX_SIGNAL); cout 最少放大器数量: answer \n; cout 放置节点: ; for (int i 0; i (int)placedNodes.size(); i) { if (i) cout ; cout placedNodes[i]; } cout \n; return 0; }注意 dfsReport 里也要做一次同样的“信号不足则放大”判断否则打印出来的信号强度会和真实状态不一致。这里的 currentSignal 是最终接收信号不是放置前的原始信号。整份代码只有三个函数加一个主函数相互之间通过全局数组传数据函数职责单一报告里也好解释。4. 常见问题与避坑最容易翻车的四个细节4.1 树的边方向搞反DFS 死循环或答案全错现象程序在递归里反复访问某些节点栈溢出或者输出的放置节点完全对不上手算结果。原因题目给的是无向边或者虽然说是树但输入顺序不保证“父节点先出现”。直接把每条边同时塞进两个节点的邻接表DFS 就会在父子之间来回走永远走不完。解决先建无向邻接表再从根节点 0 做一次 BFS根据遍历顺序确定父子和方向。通常的做法是vectorbool visited(MAXN, false); void orient(int u) { visited[u] true; for (int v : tempAdj[u]) { if (visited[v]) continue; children[u].push_back(v); orient(v); } }这样无论输入边的顺序多乱最终 children 里存的都是严格从根向外展开的有向边。数据规模不大时这个预处理成本完全可以接受。4.2 need 初值漏掉节点自身阈值现象计算出来的 need 普遍偏小导致该放放大器的地方没有放最终答案比实际需要少。原因写 dfsNeed 时把 need[u] 初始化为 0然后只和子节点的需求取 max。这样当前节点自己的阈值就被忽略了。叶子节点尤其严重它的 need 会一直是 0整个子树都变成无门槛信号。解决dfsNeed 一开始就写 need[u] thresholdVal[u]后续 max 只负责拉高不负责兜底。写完代码以后先拿叶子节点手算一遍叶子 need 必须等于自身阈值如果不等初值一定写错了。4.3 在根节点放放大器导致最优解错误现象输出结果里包含 0 号节点放大器数量比期望多 1。原因根节点是信号源放大器在根上只是把信号恢复成 MAX_SIGNAL相当于什么都没做。有的实现把根当成普通节点currentSignal 小于 need[0] 时就在根放一个白白浪费。解决dfsPlace 里明确判断 u ! 0根节点不参与放置决策。如果题目允许把放大器放在根上来“重新发射”属于题目变体但绝大多数课程设计版本没有这个设定。也可以在建模阶段把根节点的阈值设为 0并在报告里说明根不比较。4.4 递归深度过大导致爆栈现象节点数量上万或者树退化成一条链程序运行到一半直接崩溃报错信息是栈溢出。原因递归深度等于树的高度。链式树的深度能达到 n默认函数栈在 n 到几万时就撑不住了。很多同学第一次遇到这个问题会以为是算法写错其实是环境栈空间不够。解决课程设计的 n 通常在几千以内递归可以直接用但报告里要写明适用规模。如果测试数据较大就把后序遍历改成显式栈或者本地编译时加上加大栈空间的选项。最省事的做法是在代码开头加一句注释说明“本实现针对 n 10000 的树”把范围讲清楚。4.5 放大器恢复值比子树需求还小现象即使按算法在某个节点放了放大器这个节点之后的某个后代仍然不达标输出结果看起来“有解但没解完”。原因MAX_SIGNAL 是固定值如果某条链路上损耗之和太大即使把信号恢复到满格走到深处还是会跌破阈值。这种情况下问题本身无解和算法无关。解决在 dfsPlace 里放大后做一次防御判断确认 currentSignal 不小于 need[u]。如果不满足说明题目输入不保证有解程序应该输出无解标记。代码可以写成if (currentSignal need[u]) { currentSignal MAX_SIGNAL; if (currentSignal need[u]) { return; // 该子树无法被任何放大器覆盖 } }通常题目会保证初始信号强度足够大但你可以在报告里补充这个边界情况的处理作为对问题考虑的完整性证明。5. 测试样例与图表分析从单放大器到双放大器的完整验证5.1 样例一只需要一个放大器的网络沿用第 2 章的树形图输入数据如下。n 6MAX_SIGNAL 30。6 0 10 15 18 12 20 5 0 1 5 0 2 8 1 3 6 1 4 4 2 5 3先手算一遍 need 数组验证后续判断是否依赖正确的需求节点阈值need 计算过程最终 need318叶子节点18412叶子节点12110max(10, 186, 124)24520叶子节点20215max(15, 203)2300max(0, 245, 238)31从根节点 0 发出信号 30。进入节点 1 时信号是 25节点 1 的 need 是 24足够不需要放大进入节点 2 时信号是 22节点 2 的 need 是 23不够所以在节点 2 放置放大器信号恢复成 30再传给节点 5 变成 27。最终只有节点 2 放了放大器。运行结果输出最少放大器数量: 1 放置节点: 2为什么根节点 need 是 31超过 MAX_SIGNAL 却没有无解因为根节点是信号源不需要进入信号真正做决策的是根的两个子节点。这也正好验证了第 4 章说的“根节点不要参与 dfsPlace 判断”。5.2 样例二必须放两个放大器的用例再看一个更复杂的例子n 7MAX_SIGNAL 307 0 12 18 22 14 20 25 6 0 1 4 0 2 6 1 3 8 1 4 5 2 5 7 2 6 4树形图如下0(信号源) / \ (4) (6) 1 2 / \ / \ (8) (5) (7) (4) 3 4 5 6需要数组的计算结果need[3] 22need[4] 14need[1] max(12, 22 8, 14 5) 30need[5] 20need[6] 25need[2] max(18, 20 7, 25 4) 29从根发信号 30进入节点 1 是 26小于 need[1] 30所以在节点 1 放一个进入节点 2 是 24小于 need[2] 29所以在节点 2 再放一个。最终答案最少放大器数量: 2 放置节点: 1 2这个样例的意义在于说明算法不是“看哪个节点阈值高就放哪”节点 1 自己的阈值只有 12它需要放大器完全是因为子节点 3 的需求太高。如果你用朴素的自顶向下模拟一定会漏掉这种深层需求。5.3 用随机数据对拍验证正确性只靠两个样例说服力不够课程设计答辩时老师经常会问“你怎么证明程序是对的”。我的习惯是写一个暴力程序在小数据范围内和贪心结果对拍。暴力枚举所有节点的放置组合检查每种组合下所有节点是否达标再取放大器数量最小的方案。import itertools def brute(n, threshold, children, max_signal): best n 1 nodes list(range(1, n)) # 根节点不放 for mask in range(1 (n - 1)): placed [False] * n for i in range(n - 1): if (mask i) 1: placed[i 1] True signal [-10**9] * n signal[0] max_signal order [0] for u in order: for v, loss in children[u]: cur signal[u] if placed[u]: cur max_signal signal[v] cur - loss order.append(v) ok all(signal[i] threshold[i] for i in range(1, n)) if ok: cnt sum(placed) best min(best, cnt) return best对拍逻辑很简单随机生成 n 10 的树随机生成阈值和损耗分别跑贪心和暴力比较答案是否一致。跑几百组数据一旦出现不一致就用那一组输入去调试。这比人肉手算快得多也能把深层 bug 一次性揪出来。随机数据一跑很多“感觉上没问题”的玄学错误都会暴露。5.4 结果图表化输出程序跑完样例一后可以打印一张最终信号表用来验证每一个节点是否达标节点接收信号放置放大器是否达标030否根节点125否达标230是达标319否达标421否达标527否达标这张表放进课程设计报告里非常直观老师一眼就能看出每个节点的输入输出关系。样例二的信号表也可以按同样方式生成作为多放入口用例的补充材料。6. 答辩与验收从讲清楚算法到应对追问答辩时不需要把代码从头念一遍重点是讲清楚两件事为什么是两次遍历以及为什么这样放置能保证数量最少。最省时间的讲法是这样第一次后序遍历算出每个子树的最低进场需求相当于给每棵子树标了一个“门槛”第二次先序遍历从根往外发信号某节点的实际信号低于门槛时说明这个子树必须有放大器兜底放在当前节点是最深、最节省的位置。因为每个放大器都是在“不放就必有不达标节点”的情况下被迫放置的所以总数不可能再有更少方案。提前准备一张常见追问清单能显著降低答辩慌场概率。老师的提问建议回答方向为什么用后序遍历子节点需求必须先算出来父节点才能汇总取 max复杂度是多少两次遍历都是 O(n)整体 O(n)空间 O(n)放大器放在父节点行不行行但覆盖范围变大可能在不需要的分支上也生效导致多放如果信号在根上就不够怎么办根是信号源不做放置判断题目一般保证固定信号强度足够覆盖所有分支怎么证明最少每个放置都是必要性触发去掉任意一个都会让某子树跌破需求我自己的一个习惯是每回做这类课设都会在提交前强制走一遍“手算样例、跑程序、对拍随机数据、整理验收表”四步流程。手算用小样例确认算法理解正确对拍用随机数据确认没有隐蔽 bug验收表用来给报告截图和答辩展示。这个流程看起来很笨但真的能拦住绝大多数翻车现场希望帮到你。那份带完整注释、测试样例和树形图表的实现可以直接拿去做课程设计参考。本文还有配套的精品资源点击获取