简介：山东大学数据结构与算法课程设计实验中的网络放大器设置问题，完整实现与学习资料，面向正在学习图算法、准备课程设计的高校学生。资源使用C++语言编写，以加权有向无环图建模汽油传送网络，求解在最小压力约束下放置最少数量的压力放大器；代码包含详细注释，并提供多组测试样例，便于验证算法正确性。压缩包共9个文件，内含2个C++源文件、6个文本记录（测试样例、方案运行时间）和1个Markdown分析文档，整体仅4KB，结构紧凑，适合下载后直接阅读与复用。已有262人学习下载。资源重点对比了BFS与DFS两种求解思路的时间性能，BFS复杂度为O(n²)，DFS因遍历所有情况高达O(2^n)，并用图表直观显示差异；同时指出贪心局部最优策略不一定得到全局最优解，有助于深入理解算法设计复杂度与适用边界。
1. 网络放大器设置问题：一门数据结构课设到底在考你什么
某高校的《数据结构与算法》课程设计里，“网络放大器设置问题”几乎是每年都被挑走的一场大作业。拿到题的第一反应通常是：网络、链路、放大器，那不上最短路、最小生成树？真把样例手算一遍就发现，它考的不是图算法，而是你愿不愿意先把问题抽象成一条带衰减的链路，再用最朴素的顺序表和一次线性扫描去解决它。题目的显式输入是节点数、初始信号功率和每段的衰减量，隐式要求是：在最少的位置布置放大器，让整条链路上所有节点的信号都不低于某个阈值。这套方案按需求建模、数据结构设计、算法选型、C++ 实现到验收答辩的顺序展开，覆盖从敲第一行代码到讲清楚“为什么对”的全过程。
2. 需求与数据建模：先定输入输出，再谈算法
2.1 题目还原：信号衰减、阈值与放大器的定义
经典描述是一条链式通信线路，节点 1 是信号源，节点 2 到节点 n 是逐级中继接收端。信号每经过一条边就会衰减固定数值，例如经过衰减量为 3 的一段，信号就减 3。当信号降到某个阈值以下，接收端就无法正确解码，链路作废。放大器的作用是把到达该节点时的信号恢复到初始功率，之后信号继续沿链路向下传播。
这里有一个容易理解错的地方：放大器到底放在“边上”还是“节点上”。课程设计里默认放在节点上，且一个节点最多放一个。放完之后，该节点接收到的信号变成初始功率，而不是在原有信号上叠加。目标函数有两个：放大器数量最少，以及在这个数量下把每个放大器的位置输出。如果题目不要求输出唯一解，那么我一般和导师确认一次：位置取“尽量靠后”还是“尽量靠前”，样例通常按“尽量靠后”的贪心结果给。
除了基本语义，题目还隐含一个可行性约束：如果某一段的衰减量大于初始功率减阈值，那么即使这一段两端都放放大器也可能无解，因为中间没有节点可以恢复。实验题的数据通常保证单段衰减不超过这个差值，但代码里仍然要检查，遇到不合法数据直接输出 -1。
2.2 输入输出格式与必测样例
输入通常是多组样例，读到文件尾结束。每组第一行是节点数 n，第二行是初始功率 P 和阈值 R，第三行给出 n-1 个整数，代表每段链路的衰减量。输出一般是放大器总数、放置的节点编号，以及每个节点的最终信号值。
5 10 2 3 4 1 3手工推演一遍：节点 1 信号 10；过衰减 3 到节点 2 剩 7；过衰减 4 到节点 3 剩 3；过衰减 1 到节点 4 剩 2，恰好等于阈值；如果再直接过衰减 3，节点 5 就要变成 -1，链路失败。所以必须在节点 4 放一个放大器，节点 4 的信号恢复为 10，再过 3 的衰减到节点 5 剩 7。答案是 1 个放大器，位置第 4 号节点。
这个样例我建议学生全部手算一遍再编码。因为下标特别容易错：衰减数组只有 n-1 个元素，但在代码里遍历时却要和节点编号 i 对齐。如果从 0 开始读边，从 1 开始数节点，经常会出现“该放大的是节点 3，代码输出节点 4”的半对结果。
2.3 数据结构设计：Node 与 Edge 的字段约定
线性链路的建模不一定非要上邻接表，顺序表就够。我这里一般定义两个结构体：Edge 负责描述一条边，Node 负责描述节点状态。字段设计如下：
| 字段 | 类型 | 含义 |
|---|---|---|
| Edge.from | int | 边起点编号，从 1 开始 |
| Edge.to | int | 边终点编号 |
| Edge.decay | long long | 这条边带来的信号衰减量 |
| Node.power | long long | 信号到达该节点时的强度 |
| Node.amplified | bool | 该节点是否被放置了放大器 |
为什么用 long long 而不是 int？因为课程设计数据看上去不大，但一旦做压力测试，例如 n 到十万、每段衰减量上万，累加值很快超过 int 范围。用 long long 只是多写两个字母，却能避免答辩时被随机大数据问倒。
如果是树形网络的扩展场景，才需要把顺序表换成邻接表以及做一次 DFS。线性链路的本质是单一路径，顺序表加下标访问就是最自然的结构，不必为了“显得高级”强行引入图结构。数据结构选型不是堆砌，而是匹配问题的形状。
3. 总体设计：贪心策略、DP 变体与复杂度取舍
3.1 把问题压缩成区间覆盖：可用余量 P-R
整条链路能不能走通，只取决于一个数：初始功率 P 与阈值 R 的差值 P-R。这个差值代表“信号从被恢复之后可以容忍的最大总衰减量”。每经过一条边，就从可用余量里扣掉一个衰减值；一旦某个节点上的累计衰减超过 P-R，该节点信号就会低于阈值。
所以问题本质变成了一个区间覆盖问题：链路上的每一段都必须被某一个放大器“覆盖”，并且两个相邻放大器之间的衰减总量不能超过 P-R。判断条件里用的是“超过”而不是“大于等于”，因为题目语义一般是“不低于阈值”，等于阈值是允许的。如果导师要求“严格大于阈值”，只需要把判断符号改一处。
把问题翻译成这句话之后，很多人会自然想到二分答案、动态规划或者暴力搜索，但都没有必要。这些方法能解决更一般的变体，却无法突出这道题贪心的简洁性。
3.2 贪心算法：从左到右只扫一遍
贪心策略是线性扫描：从节点 1 出发，维护一个 loss 变量，表示离最近一个放大器已经累计衰减了多少。每次准备经过边 i 时，先检查 loss 加这条边的衰减量是否大于 P-R。如果大于，说明再不放放大器，下一个节点就撑不住了，那么必须把放大器放在当前节点 i 上，并把 loss 清零。
信号到达节点 1，loss = 0 for i = 1 到 n-1： 如果 loss + 衰减量[i] > P - R： 在节点 i 放置放大器 loss = 0 loss = loss + 衰减量[i] 节点 i+1 的信号 = P - loss为什么放在当前节点而不是下一节点？因为下一节点是接收端，信号到达它时已经衰减过了，再在它身上放放大器虽然也能恢复，但这段衰减仍然浪费了一次“被放过”的机会。放在当前节点，等于把恢复点前移一段，能覆盖后续更多边。这也是贪心解的直观来源。
这个算法的正确性可以用交换论证说清楚：对于任意最优解，把它的第一个放大器位置和贪心解的第一个放大器位置比较。贪心选择的放大器一定不会比最优解更靠前，因为贪心在还能走通的情况下绝不放置；因此贪心解第一个放大器覆盖的区间长度不短于最优解。接下来从该放大器出发，对剩余的链路重复同样的论证，贪心解每轮的覆盖范围都不短于最优解，所以总放大器数不会多于最优解，也就是最优。
3.3 为什么不是回溯，也不是拆成最短路径
回溯枚举的复杂度是 2 的 n 次方，n 到二十就明显吃力。最短路模型又要求我们把“衰减”映射成边权，把“放大器”映射成路径上的恢复点，反而要把链路拆成多层状态，实现麻烦且没有体现出数据结构课程设计的重点。线性扫描不需要额外空间，时间复杂度 O(n)，空间 O(n) 用于记录节点信号，这才是这道题作为课程设计的合理深度。
3.4 带节点成本的 DP 扩展：当贪心失效时
如果题目改成每个节点放置放大器的成本不同，或者放大器恢复后的功率不是固定值，贪心就不成立了。此时需要动规。一种常见改法是：节点 i 放置放大器的代价为 cost[i]，求最小总代价。定义 dp[i] 表示前 i 个节点都合规，且节点 i 放置了放大器的最小代价，转移时枚举上一个放大器所在位置 j，要求 j 到 i 之间的衰减总量不超过 P-R。
dp[1] = cost[1] for i = 2 到 n： dp[i] = 无穷大 for j = 1 到 i-1： 如果 从 j 到 i-1 的衰减总和 <= P - R： dp[i] = min(dp[i], dp[j] + cost[i]) 答案 = min(dp[n], dp[n-1], ...)这个扩展不要求写在基础版代码里，但很适合写进设计报告的“算法对比”一节。我在答辩时见到最稳妥的一类学生，都是先讲清楚基本版贪心为什么最优，再补一句“若引入节点成本，问题升级为线性动态规划，复杂度 O(n²)”。只讲贪心显得单薄，只讲 DP 又显得没抓住实验题本意。
三种算法的取舍可以归纳成一张表：
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 贪心扫描 | O(n) | O(n) | 放大器恢复固定功率，成本相同 |
| 动态规划 | O(n²) | O(n) | 节点成本不同，恢复策略不同 |
| 回溯枚举 | O(2^n) | O(n) | 仅 n <= 20 的验证场景 |
4. C++ 模块实现：工程结构、核心代码与图表输出
4.1 工程文件划分与输入解析
工程不需要做成一个大 main 文件。为了课程设计报告好看，也为了自己调试省事，我一般按四层来分：结构体定义、求解器、输入输出、测试数据。
amplifier/ ├── solver.h # Node、Edge、AmplifierSolver 声明 ├── solver.cpp # 贪心与校验实现 ├── main.cpp # 读取输入，调用求解器，输出结果 ├── export_csv.cpp # 导出画图数据 ├── testcases/ │ ├── in1.txt # 基础样例 │ ├── in2.txt # 单段衰减恰好等于 P-R │ └── in3.txt # n 较大时压力样例输入读取用 C++ 标准流即可，多组样例用 while 循环。这里最容易踩坑的是空行和无效输入。稳健做法是逐项读整数而不是逐行读字符串，因为样例文件里可能有注释行或空行干扰 getline 解析。
4.2 核心贪心求解器实现
下面是求解器的核心代码，注释已经按课程设计汇报的要求写清楚了，关键判断逻辑集中在 solve 函数里。
#include <bits/stdc++.h> using namespace std; struct Edge { int from, to; // 边的两端节点编号，1-based long long decay; // 该段链路的信号衰减量 }; struct Node { long long power; // 到达该节点时的信号强度 bool amplified; // 该节点是否需要放置放大器 }; class AmplifierSolver { private: int n; // 节点总数 long long power; // 初始信号功率 P long long threshold; // 阈值 R vector<Edge> edges; // 链路段，共 n-1 条 vector<Node> nodes; // 每个节点的信号状态 vector<int> placed; // 记录放大器位置 long long budget; // 可容忍总衰减量 P-R public: AmplifierSolver(int n_, long long p_, long long th_, const vector<long long>& decays) : n(n_), power(p_), threshold(th_) { budget = power - threshold; // 把一维衰减数组映射成边结构 for (int i = 1; i < n; ++i) { edges.push_back({i, i + 1, decays[i - 1]}); } nodes.resize(n + 1); placed.clear(); } int solve() { long long loss = 0; // 距最近放大器已累计衰减 nodes[1].power = power; // 信号源 for (int i = 1; i < n; ++i) { // 进入第 i 段之前判断当前节点 i 是否需要承担放大器 if (loss + edges[i - 1].decay > budget) { nodes[i].power = power; nodes[i].amplified = true; placed.push_back(i); loss = 0; } // 正常经过这一段 loss += edges[i - 1].decay; nodes[i + 1].power = power - loss; } return (int)placed.size(); } // 校验最终链路每个节点信号是否合规 bool verify() const { for (int i = 1; i <= n; ++i) { if (nodes[i].power < threshold) return false; } return true; } const vector<int>& getPlaced() const { return placed; } const vector<Node>& getNodes() const { return nodes; } };这段代码里有三个细节值得在报告里单独说明。第一个是判断时机：必须在“经过第 i 段之前”判断，而不是在算出下一个节点信号之后再去补救。第二个是 loss 清零后，节点 i 的信号已经被覆盖成初始功率，所以 CSV 导出时不能直接沿用循环之前的值。第三个是 edges 用 vector 按下标访问，而不是用链表，因为这里不需要增删边，顺序表对随机访问更友好。
4.3 结果校验与 CSV 导出
写完贪心后不能只看输出数量，还要强制跑一遍 verify。把最终信号打印到文件，逐项对比阈值，这一步能杜绝绝大多数半路翻车。
void exportCSV(const string& path) { ofstream fout(path); fout << "node,signal,amplifier\n"; for (int i = 1; i <= n; ++i) { fout << i << "," << nodes[i].power << "," << (nodes[i].amplified ? 1 : 0) << "\n"; } }CSV 文件格式是 node、signal、amplifier 三列，amplifier 字段为 1 表示该节点放放大器。这个文件既可以直接交给导师看，也能喂给 Python 脚本画图。
4.4 用 Matplotlib 画信号衰减曲线
图表部分是课程设计报告里比较出彩的模块。我一般用 Python 读 CSV，画出信号随节点变化的折线，同时把放大器节点用散点标记出来。
import pandas as pd import matplotlib.pyplot as plt df = pd.read_csv("signal_curve.csv") plt.figure(figsize=(8, 4)) plt.plot(df["node"], df["signal"], marker="o", label="signal") amp = df[df["amplifier"] == 1] plt.scatter(amp["node"], amp["signal"], color="red", s=80, label="amplifier") plt.axhline(y=df["signal"].min(), color="gray", linestyle="--", linewidth=1) plt.xlabel("node") plt.ylabel("signal power") plt.legend() plt.grid(True) plt.savefig("signal_curve.png", dpi=150)绘图脚本不参与课程要求的算法实现，但它能直观看出放大器放在哪里、信号在哪几个节点被恢复。答辩时放一张图，比念十行输出结果更有说服力。
4.5 一份可读的输出样例
以第 2 章的样例为例，跑完程序后输出表格化的内容如下：
| 节点编号 | 信号强度 | 是否放置放大器 | 说明 |
|---|---|---|---|
| 1 | 10 | 否 | 信号源 |
| 2 | 7 | 否 | 经过衰减 3 |
| 3 | 3 | 否 | 经过衰减 4 |
| 4 | 10 | 是 | 放大器恢复信号 |
| 5 | 7 | 否 | 经过衰减 3 |
这个表格放进设计报告的实验结果节，再配上一张信号曲线图，输出的完整性就够了。
5. 常见问题与避坑：测试全过不代表能答辩
5.1 放大器数量总是差一个：边界条件写错位置
现象：样例都能跑通，但自己随手改一个衰减量，输出放大器数就比手算少一个或多一个。
原因：把判断放在了“下一个节点信号算出来之后”，导致放大器的位置比真正需要的位置晚了半拍。例如走到节点 i+1 发现信号已经低于阈值，才在节点 i+1 放放大器，但真正应该在节点 i 放。
解决：严格按照“进入某段之前判断”的逻辑。放大器的恢复效果发生在当前节点，覆盖的是接下来那一段，不是已经走过的段。
5.2 输入样例一直死循环：多组样例的读入坑
现象：程序读取第二组样例时读到了第一组末尾残留的换行或空行，导致解析错位，甚至 while 循环读不到 EOF。
原因：用 getline 按行读取时，行末回车没有处理好；或者输入文件里混了注释和空行。
解决：直接用while (cin >> n)读整数，让标准流自动跳过空白字符。这能避免 90% 的输入解析问题。
5.3 int 溢出和负信号：数据范围别省
现象：n 只有一千时程序正常，换到 n 十万的测试数据，信号值突然变成奇怪的大负数。
原因：衰减量累加超过了 int 范围，或者在某处把 long long 强制转换成了 int。
解决：所有信号量和衰减量统一用 long long。写代码时从结构体字段到临时变量都用同一类型，杜绝隐式转换。
5.4 曲线图上的放大器位置不对：忘了覆盖节点信号值
现象：CSV 里信号曲线是对的，但放大器标记点却落在阈值线下方。
原因：放置放大器后，没有把该节点的 power 字段重新赋值为 P，导出的节点信号还是放大前的旧值。
解决：在 placed.push_back(i) 旁边同步执行 nodes[i].power = power。每次插入放大器位置的代码块里都要带上这一行，不要只维护 placed 数组。
5.5 只验证样例不验证最优性：对拍器才是后悔药
现象：几个手写样例全过，答辩时被问“你怎么证明最少”，只能支支吾吾。
原因：没有做正确性验证，把样例通过当成了完整验收。
解决：写一个 n 不超过 20 的暴力枚举程序，枚举所有放大器的放置子集，找出合法解里数量最少的一个；再随机生成几百组小数据，让暴力程序和贪心程序对拍。两者输出不一致，就说明贪心或暴力至少有一个错了。这套对拍流程不到一百行，却能救回答辩现场最尴尬的问题。
6. 测试、验收与答辩：把方案从“能跑”变成“无懈可击”
6.1 验收清单与测试用例设计
课程设计验收不能只看最终结果。我一般把测试分成四类：基础样例、边界样例、压力样例、错误样例。基础样例就是题目给的数据，验证功能；边界样例覆盖“衰减量恰好等于 P-R”“P 等于 R”“所有段衰减总量刚好在阈值之内”三种情况；压力样例用十万级节点验证时间复杂度；错误样例故意让单段衰减超过 P-R，验证程序输出 -1 而不是崩溃。
| 用例类型 | 输入要点 | 期望结果 |
|---|---|---|
| 基础样例 | n=5，P=10，R=2，衰减 3 4 1 3 | 1 个放大器，节点 4 |
| 边界样例 | 某段衰减恰为 P-R | 不放置放大器也能过 |
| 压力样例 | n=100000，随机衰减 | 线性扫描，秒级出结果 |
| 错误样例 | 单段衰减大于 P-R | 输出 -1 |
6.2 随机数据对拍：让程序自己和自己打架
对拍脚本很短，但价值很高。暴力程序枚举所有子集，对每个合法方案统计放大器数量，取最小值；贪心程序跑同一组输入。用循环生成随机 n 和随机衰减量，比较两份输出。一旦发现不一致，就缩小到那组随机数据手动排查。这个流程能把“我觉得最优”变成“程序验证过最优”。
6.3 答辩时最可能被追问的五个问题
每次答辩都会围绕“为什么”展开，而不是围绕“怎么写的”展开。我整理了五个高频追问：
- 为什么贪心得到的一定是最少的放大器数？用交换论证：贪心每次选择的恢复点不早于任何最优解的同序恢复点，覆盖范围只长不短。
- 如果每个节点放大器成本不同怎么办？回答线性 DP 扩展，复杂度 O(n²)，说明你已经想清楚了贪心的适用边界。
- 时间复杂度和空间复杂度分别是多少？O(n) 时间、O(n) 空间。
- 为什么用顺序表而不是链表？因为这里只有按下标访问，没有插入删除。
- 如果某一段衰减超过 P-R 怎么办？输出 -1，并说明该链路单独一段就无法满足阈值。
答辩前把所有输出都重新跑一遍 verify，把 CSV 和曲线图再生成一次。从那以后，我每次做课程设计都强制走一遍对拍和边界测试，半路翻车的概率明显小了很多。这份方案的完整工程文件、测试样例和绘图脚本已打包在资源里，下载后按 README 编译即可复现所有结果，希望帮到你。
本文还有配套的精品资源，点击获取
