简介这份资源面向山东大学数据结构与算法课程设计的学习者聚焦实验四「网络放大器设置问题」的完整求解方案。题目以加权有向无环图描述汽油传送网络要求在保证最小压力Pmin的前提下用最少数量的放大器使相邻放大器间距离不超过d属于典型的图论与贪心策略综合训练。压缩包共9个文件约4KB包含2个cpp源码文件、6个txt测试样例与计时数据、1个md说明文档源码附有详细注释样例覆盖多组输入场景便于对照调试与验证。资源还针对BFS与DFS两种思路进行时间性能对比用图表呈现结果并指出BFS时间复杂度为O(n²)、DFS为O(2^n)贪心算法虽能提供局部最优策略但不一定得到全局最优解。目前已有262人学习适合需要完成同类课程设计、理解图搜索与贪心取舍的读者参考。1. 从一道“网络放大器”题说起这套课设方案到底要解决什么如果你正在做数据结构与算法课程设计大概率会遇到一类题给定一张网络拓扑图节点代表路由器或交换机边代表链路每条边有信号衰减或成本现在要选若干位置放置“放大器”让所有节点之间的通信质量达标同时放大器数量或总代价最小。这道网络放大器设置问题本质上是图论里的组合优化问题涉及图的存储、遍历、最短路径或最小生成树等经典算法。很多人第一反应是暴力枚举所有放置方案但节点数一上来组合爆炸直接让程序跑不动。这套山东大学数据结构与算法课程设计的实验方案就是围绕这个问题给出从建模、算法选择到 C 实现、测试样例和图表分析的完整交付物。它适合正在赶课设的学生直接参考结构也适合想复习图论算法落地的开发者拿去做练手项目。关键词里提到的“网络放大器”“数据结构与算法”“课程设计”“C”在这套方案里都有对应的模块和代码支撑不是空壳。2. 需求拆解与模型抽象把现实问题翻译成图论语言2.1 问题边界与输入输出定义拿到题目先别急着写代码我一般会先把输入输出格式钉死。网络放大器设置问题通常给出一张无向带权图第一行是节点数 n 和边数 m接下来 m 行每行三个整数 u、v、w表示节点 u 和 v 之间有一条链路信号经过这条链路会衰减 w 个单位。再给一个阈值 T表示任意两个节点之间的累计衰减不能超过 T。要求选出最少的节点放置放大器使得任意两个节点之间的最短路径衰减都不超过 T。输出就是放大器数量以及具体放置的节点编号。这个定义里有两个容易翻车的点一是“任意两个节点”意味着要检查全源最短路径不是单源二是放大器放在节点上效果是让经过该节点的路径衰减归零还是减半题目通常会有明确说明但很多同学读题时直接忽略导致后面算法全错。我一般会在代码里用一个布尔数组hasAmp标记节点是否放置然后在计算路径衰减时根据这个数组调整权重。2.2 为什么选 C 而不是 Python课设题目指定 C 是有道理的。图论算法里经常需要开二维数组做邻接矩阵节点数到几百甚至上千时Python 的列表嵌套列表内存开销和访问速度都会成为瓶颈。C 的vectorvectorint或者静态二维数组在性能上更可控而且 STL 里的priority_queue直接能拿来做 Dijkstra 的堆优化。另外课设通常要求提交可编译运行的源码C 的编译型特性让老师验收时更放心不会出现“你环境里能跑我这儿跑不了”的尴尬。2.3 核心算法选型Floyd 还是 Dijkstra全源最短路径经典算法就两个Floyd-Warshall 和 Johnson。Floyd 写起来简单三重循环核心代码不到十行时间复杂度 O(n^3)。如果节点数 n 不超过 300Floyd 完全够用而且代码可读性强老师一看就懂。Dijkstra 跑 n 次也能求全源复杂度 O(n*(mn)logn)稀疏图下更快但代码量翻倍还要处理堆和距离数组的初始化。我一般会这样决策先看题目给的 n 范围。如果 n ≤ 200直接上 Floyd省事且不容易出错如果 n 到 1000 以上再考虑 Dijkstra 堆优化。这套课设方案里测试样例的节点数都在 100 以内所以 Floyd 是更稳妥的选择。下面这段代码就是 Floyd 的核心实现注意三层循环的顺序不能乱k 必须放最外层。// Floyd-Warshall 求全源最短路径 // dist[i][j] 初始为邻接矩阵无边设为 INF for (int k 0; k n; k) { // 中间节点 for (int i 0; i n; i) { // 起点 for (int j 0; j n; j) { // 终点 if (dist[i][k] ! INF dist[k][j] ! INF) { dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); } } } }这段代码的逻辑是每次允许经过节点 k 作为中转更新所有点对之间的最短距离。参数dist是二维数组INF取一个足够大的数比如0x3f3f3f3f防止加法溢出。循环顺序如果写错比如把 k 放最内层结果就是错的这是血泪经验。2.4 放大器放置策略的建模有了全源最短路径接下来要决定放大器放哪里。最直接的做法是贪心每次找一个节点假设放上放大器后能最大程度减少“超标”的节点对数量然后重复直到所有点对都达标。但贪心不一定最优所以课设里通常允许用暴力搜索或者状态压缩 DP 来求精确解。如果节点数 n ≤ 20可以用二进制枚举所有子集检查每个子集是否能让所有点对达标取最小的子集大小。如果 n 更大那就只能用贪心或者启发式搜索然后在报告里说明这是近似解。我一般会在代码里把两种策略都实现然后对比测试样例上的结果。这样写报告时也有东西可写精确解在小规模下验证贪心的近似比图表一画分析就出来了。3. 总体架构与模块划分从输入解析到结果输出3.1 工程目录与文件职责一个能拿得出手的课设代码不能全堆在main.cpp里。我一般会拆成这几个文件graph.h/graph.cpp图的存储结构邻接矩阵的初始化、加边、打印。algorithm.h/algorithm.cppFloyd 算法、放大器放置的贪心和暴力搜索。io.h/io.cpp从文件或标准输入读取图数据输出结果到文件。main.cpp主流程调度读配置、跑算法、输出。test/目录放测试样例每个样例一个.in文件和一个.out文件。这样拆的好处是老师检查代码时能一眼看出模块边界你自己调试时也能单独测每个部分。比如 Floyd 写完了先拿一个简单图跑一下确认最短路径矩阵对了再去写放大器放置逻辑。3.2 图存储结构的设计取舍邻接矩阵和邻接表怎么选如果后面要用 Floyd那必须用邻接矩阵因为 Floyd 本身就是基于矩阵的。如果要用 Dijkstra 堆优化邻接表更省空间。这套方案里我选邻接矩阵原因有三一是节点数不大二维数组内存可控二是 Floyd 代码简洁三是放大器放置时需要频繁查询任意两点间距离矩阵 O(1) 访问比邻接表遍历快得多。矩阵初始化时对角线设为 0有边的位置设为权值无边设为INF。注意如果图里有重边要取最小的那条这是常见坑。// 邻接矩阵初始化 const int INF 0x3f3f3f3f; vectorvectorint dist(n, vectorint(n, INF)); for (int i 0; i n; i) dist[i][i] 0; // 读入边 for (int i 0; i m; i) { int u, v, w; cin u v w; u--; v--; // 如果题目节点从 1 开始编号 dist[u][v] min(dist[u][v], w); dist[v][u] min(dist[v][u], w); // 无向图 }这段代码里min的作用就是处理重边只保留最小权值。节点编号减一是因为题目通常从 1 开始而 C 数组从 0 开始这个转换不做的话后面全乱。3.3 放大器放置的暴力搜索实现当 n ≤ 20 时二进制枚举所有放置方案是可行的。总共有 2^n 种可能每种方案检查一次全源最短路径是否达标复杂度 O(2^n * n^2)。n20 时大约是 100 万次操作C 一秒内能跑完。// 二进制枚举所有放大器放置方案 int bestCnt n 1; vectorint bestSet; for (int mask 0; mask (1 n); mask) { int cnt __builtin_popcount(mask); if (cnt bestCnt) continue; // 剪枝已经不比当前最优好 // 复制一份距离矩阵应用放大器效果 vectorvectorint d dist; for (int k 0; k n; k) { if (mask (1 k)) { // 假设放大器让经过 k 的路径衰减归零 for (int i 0; i n; i) for (int j 0; j n; j) d[i][j] min(d[i][j], d[i][k] d[k][j]); } } // 检查是否所有点对都达标 bool ok true; for (int i 0; i n ok; i) for (int j 0; j n ok; j) if (d[i][j] T) ok false; if (ok) { bestCnt cnt; bestSet.clear(); for (int k 0; k n; k) if (mask (1 k)) bestSet.push_back(k 1); } }这里__builtin_popcount是 GCC 内置函数统计二进制里 1 的个数用来算放大器数量。剪枝那行很关键如果当前方案已经用了比最优解更多的放大器直接跳过能省不少时间。放大器效果这里假设是让经过该节点的路径衰减归零具体题目怎么定义就怎么改。3.4 贪心策略作为大规模输入的备选如果 n 超过 20二进制枚举就爆了。这时候用贪心每次选一个节点放放大器选那个能让“超标点对数量”下降最多的节点直到全部达标。贪心不保证最优但速度快O(n^3) 左右。写报告时可以拿小规模数据对比贪心和精确解算一下近似比这也是一个分析点。// 贪心选择放大器位置 vectorint greedy(int n, vectorvectorint dist, int T) { vectorint amps; while (true) { // 检查是否全部达标 bool ok true; for (int i 0; i n ok; i) for (int j 0; j n ok; j) if (dist[i][j] T) ok false; if (ok) break; // 选一个能最大程度减少超标点对的节点 int bestNode -1, bestReduce -1; for (int k 0; k n; k) { if (find(amps.begin(), amps.end(), k) ! amps.end()) continue; int reduce 0; for (int i 0; i n; i) for (int j 0; j n; j) if (dist[i][j] T dist[i][k] dist[k][j] T) reduce; if (reduce bestReduce) { bestReduce reduce; bestNode k; } } if (bestNode -1) break; // 无法再改善 amps.push_back(bestNode); // 更新距离矩阵 for (int i 0; i n; i) for (int j 0; j n; j) dist[i][j] min(dist[i][j], dist[i][bestNode] dist[bestNode][j]); } return amps; }这段贪心的核心是每次选“边际收益”最大的节点。reduce统计的是放上这个节点后有多少原本超标的点对变得达标。选完之后更新距离矩阵继续下一轮。注意如果某一轮找不到能改善的节点说明问题无解直接退出。4. 避坑与常见问题排查课设里最容易翻车的五个点4.1 节点编号从 0 还是 1 开始现象程序在小样例上跑出正确结果换一个样例就全错。原因题目输入节点编号从 1 开始但代码里数组下标从 0 开始读入后忘了减一导致访问越界或者结果偏移。解决在读取边的时候统一做u--; v--;输出结果时再1还原。我一般会在代码里写一行注释// 题目节点从 1 开始内部统一转 0-based提醒自己。4.2 INF 取值太小导致加法溢出现象Floyd 跑完某些点对距离变成负数或者奇怪的小值。原因INF取INT_MAX两个INF相加直接溢出变成负数然后min取到了这个负数。解决INF取0x3f3f3f3f大约是 10 亿两个相加不超过int上限而且足够大不会和真实距离混淆。这是经典技巧课设里老师也会看这个细节。4.3 放大器效果理解错误现象放置方案看起来合理但达标检查总是不通过。原因题目说“放大器让信号衰减减半”你按“归零”算或者反过来。解决读题时把放大器效果那句话圈出来在代码里单独写一个函数applyAmp(dist, k)把效果逻辑集中在一处改起来方便。测试时手动构造一个简单图人肉算一遍预期结果和程序输出对比。4.4 暴力枚举没剪枝导致超时现象n20 时程序跑了几分钟没出结果。原因2^20 约 100 万种方案每种方案都完整复制矩阵并跑一遍检查常数太大。解决加剪枝当前方案放大器数量已经大于等于已知最优解时直接跳过另外可以按放大器数量从小到大枚举找到第一个可行解就停。我一般还会把距离矩阵的复制改成增量更新减少内存操作。4.5 测试样例覆盖不全现象自己测了几个样例都过老师一测就挂。原因只测了连通图没测不连通图只测了有解的情况没测无解只测了小规模没测边界。解决至少准备五类样例——普通连通图、不连通图、无解图、单节点图、重边图。每类样例手动算好预期输出写成.out文件用脚本批量对比。这样答辩时老师随机抽样例你也能稳过。5. 验收与答辩怎么证明你的方案是靠谱的5.1 测试样例的设计与批量验证课设验收时老师通常会拿几个你没见过的样例来跑。所以你的程序不能只对特定输入有效得经得起随机测试。我一般会写一个简单的生成器随机生成 n 个节点、m 条边的图权值在 1 到 100 之间然后跑你的程序再用一个暴力但正确的参考程序跑一遍对比结果。如果几百组随机测试都一致那基本就稳了。# 批量测试脚本示例 for i in $(seq 1 100); do python3 gen.py test.in # 生成随机样例 ./my_solution test.in my.out ./brute_force test.in ref.out if ! diff -q my.out ref.out /dev/null; then echo Test $i failed break fi done echo All tests passed这个脚本的逻辑很直接生成样例分别跑你的程序和参考程序对比输出。gen.py里控制节点数在 10 到 15 之间这样暴力参考程序也能秒出。如果 100 组都过说明你的核心逻辑没问题。5.2 图表与复杂度分析怎么写课设报告里通常要求画图。我一般会画两张一张是节点数 n 和运行时间的关系曲线用不同规模的随机图测出来另一张是贪心解和精确解的放大器数量对比展示近似比。画图用 Python 的 matplotlib 或者 Excel 都行数据从程序里输出成 CSV再导入画图工具。复杂度分析要写清楚Floyd 是 O(n^3)二进制枚举是 O(2^n * n^2)贪心是 O(n^3) 左右。然后结合测试数据说明n ≤ 20 时用精确解n 20 时用贪心这样在报告里体现你有工程取舍的意识。5.3 答辩时怎么讲清楚你的设计答辩不是让你念代码而是讲清楚三件事问题是什么、你怎么建模、为什么选这个算法。我一般会准备一页 PPT左边画原始网络拓扑图右边画抽象后的带权图中间用箭头标注“节点→顶点链路→边衰减→权值”。然后讲算法选型时直接说“n 小于等于 20 我用二进制枚举保证最优n 更大我用贪心保证速度”老师一听就知道你思考过。如果老师问“为什么不用动态规划”你可以说“状态压缩 DP 也可以但二进制枚举更直观而且 n 小的时候两者复杂度差不多课设里优先选可读性强的方案”。这种回答既展示了知识面又说明了工程取舍。5.4 我踩过的坑和现在的习惯有一次我帮别人看课设他的程序在小样例上跑得飞快结果老师给了一个 n50 的样例直接卡死。原因是他用了二进制枚举但没加剪枝2^50 根本跑不完。从那以后我每次写组合优化类题目都强制先问自己三个问题n 最大多少精确解复杂度能不能接受不能接受的话近似策略是什么这三个问题想清楚了再动手写代码能省掉大量返工时间。希望这套方案能帮你把网络放大器设置问题理清楚从建模到代码到验收每一步都有可参考的落地细节。本文还有配套的精品资源点击获取