简介：山东大学数据结构与算法课程设计实验四“网络放大器设置问题”的完整实现包，面向高校数据结构与算法课程学习者及需要完成相似图论实验的同学。资源基于加权有向无环图建模汽油传送网络，围绕最小压力Pmin与最大压力Pmax的约束，求解放置放大器的最少数量。包内共9个文件，含2个C++源文件（实验主程序与时间性能测试）、6个txt文本（多组测试样例及两种方案的运行时间记录）和1个md说明文档，整体仅4KB，便于快速下载查阅。已有262人学习使用。代码附带详细注释，并分别采用BFS（O(n²)）与DFS（O(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++ 实现时，我一般选择 vector<Edge> 数组来存子节点，而不是邻接矩阵。原因有两个：一是树是稀疏图，n 个节点只有 n-1 条边，用 n 乘 n 的邻接矩阵浪费空间，节点数量上万时内存直接爆掉；二是后序和先序两次遍历都需要频繁访问某个节点的所有子节点，邻接表刚好能做到高效枚举。

const int MAXN = 10005; struct Edge { int to; // 子节点编号 int loss; // 这条链路上的信号损耗 }; vector<Edge> 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 整体流程：四个模块的职责划分

整套程序按四个模块拆开，每个模块的职责可以单独测试。

1. 输入模块：读入 n、阈值数组、m 条边三元组，建立 children 邻接表。
2. 需求计算模块：调用 dfsNeed 做后序遍历，计算每个节点的 need[u]。
3. 放置决策模块：调用 dfsPlace 做先序遍历，携带实际信号判断是否需要放放大器。
4. 结果输出模块：打印放大器数量、放置节点列表，以及每个节点最终接收到的信号强度表。

调用顺序只有一种：先 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; // 链路损耗 }; vector<Edge> children[MAXN]; int thresholdVal[MAXN]; // 节点接收阈值 int need[MAXN]; // 子树最低进场需求 int answer = 0; vector<int> 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 自底向上的需求计算 dfsNeed

dfsNeed 用后序遍历实现：先递归处理所有子节点，再回到当前节点汇总需求。某个子节点 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 自顶向下的放置决策 dfsPlace

dfsPlace 携带一个 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，根据遍历顺序确定父子和方向。通常的做法是：

vector<bool> 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 = 6，MAX_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 数组，验证后续判断是否依赖正确的需求：

从根节点 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 = 7，MAX_SIGNAL = 30：

7 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] = 22
• need[4] = 14
• need[1] = max(12, 22 + 8, 14 + 5) = 30
• need[5] = 20
• need[6] = 25
• need[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 结果图表化输出

程序跑完样例一后，可以打印一张最终信号表，用来验证每一个节点是否达标：

这张表放进课程设计报告里非常直观，老师一眼就能看出每个节点的输入输出关系。样例二的信号表也可以按同样方式生成，作为多放入口用例的补充材料。

6. 答辩与验收：从讲清楚算法到应对追问

答辩时不需要把代码从头念一遍，重点是讲清楚两件事：为什么是两次遍历，以及为什么这样放置能保证数量最少。

最省时间的讲法是这样：第一次后序遍历算出每个子树的最低进场需求，相当于给每棵子树标了一个“门槛”；第二次先序遍历从根往外发信号，某节点的实际信号低于门槛时，说明这个子树必须有放大器兜底，放在当前节点是最深、最节省的位置。因为每个放大器都是在“不放就必有不达标节点”的情况下被迫放置的，所以总数不可能再有更少方案。

提前准备一张常见追问清单，能显著降低答辩慌场概率。

我自己的一个习惯是：每回做这类课设，都会在提交前强制走一遍“手算样例、跑程序、对拍随机数据、整理验收表”四步流程。手算用小样例确认算法理解正确，对拍用随机数据确认没有隐蔽 bug，验收表用来给报告截图和答辩展示。这个流程看起来很笨，但真的能拦住绝大多数翻车现场，希望帮到你。那份带完整注释、测试样例和树形图表的实现，可以直接拿去做课程设计参考。

本文还有配套的精品资源，点击获取