PAT甲级里有一类题名字里都带着“Supply Chain”。我第一次看到 Total Sales of Supply ChainA1079的时候被供应商、经销商、零售商这些商业概念唬住了以为要模拟一套复杂的中间商加价流程。其实把业务外壳剥掉这就是一棵非常标准的树根是原始供应商中间节点是经销商叶子是零售商价格从根往下一层层乘系数上涨。这道题的要求很明确输入整棵供应链的结构和每个零售商的销量算出全渠道的总销售额。25分的分值在甲级里属于中坚题型考察建树、遍历深度、浮点累加三个基本功还附带了一堆输入输出细节的坑。这篇文章就把整个拆解过程、两版可直接用的代码和调试中遇到的坑讲清楚适合正在刷PAT树的板块、或者复习DFS/BFS的人参考。1. 先把供应链故事翻译成数据结构题目输入到底在说什么1.1 供应商、经销商、零售商本质是一棵有向树从业务角度看供应链是一条从源头到终端的链路原始供应商把货批发给经销商经销商可能再分给下一级经销商最终到零售商手里卖给顾客。题目里把每条“加价路径”抽象成了树结构节点编号从0到N-1其中0号固定是根供应商也就是整棵树的入口。为什么强调是“树”因为树结构意味着每个节点只有一个父节点不存在环路从根出发可以到达所有节点。这种结构决定了我们只需要沿着父亲往下走不需要处理方向问题也不需要处理环的问题。实际建图的时候输入给的是每一行的“孩子列表”没有直接给父亲所以本质上这是一个邻接表式的有向树方向从父节点指向子节点。我后来做题的经验是不要一上来就试图用链表、二叉树之类的花哨结构去套它。节点的孩子数量完全不确定可能一个节点有几十个孩子也可能一个孩子都没有最自然的方式是给每个节点开一个动态数组存孩子。这样既符合输入格式也方便后续遍历。1.2 输入行的两种形态内部节点与叶子节点的区分这道题输入格式的第一行固定是三个数N节点总数、P根供应商的初始单价、r每一层涨价的百分比。接下来有N行第i行描述节点i的孩子关系而且只有两种形态。第一种形态是 Ki 大于0说明节点i是内部节点也就是供应商或经销商它后面跟着 Ki 个整数是它直接下级的编号。第二种形态是 Ki 等于0说明节点i是零售商没有下级它后面跟着一个浮点数表示这个零售商的销量。我在第一次读题时犯过一个低级错误想当然地认为Ki等于0时后面可能还有孩子编号于是把读入逻辑写成了“先读Ki再循环读Ki个数”结果在Ki等于0的行里多读了一个销量当成孩子编号整个数据全乱了。实际上这道题的读入逻辑就是分支的如果Ki为0读一个double存销量如果Ki大于0循环读Ki个int存孩子。用scanf处理这种混合格式非常顺手因为scanf天然会跳过空格和换行。举个最简单的例子帮你建立直观认识输入3 100.0 10.0 2 1 2 0 10 0 2第0行表示0号节点有两个孩子分别是1和2第1行Ki为0说明1号是零售商销量10第2行同样说明2号是零售商销量2。根供应商定价100涨价10%那么1号和2号的销售单价都是110总销售额就是110×10加上110×2等于1320。这个例子后面做代码验证时会一直用到。2. 从根价格到叶子价格那个公式里藏着几个必踩的坑2.1 逐层涨价不是加法而是指数计算销售价格的核心公式看起来很简单如果某个零售商所在的层数是d那它的售价就是P × (1 r/100)^d问题是很多人会把涨价理解成加法误写成 P d × P × r/100。这两者差别很大。举个例子P100r10到达第2层时正确价格是100×1.1×1.1121如果用加法算会得到1002×10120答案直接错了。为什么是指数而不是加法因为题目的描述是“每经过一级经销商售价增加r%”这个r%是在当前售价基础上增加的不是在最初进价基础上加的。也就是说第1层的价格是 P×(1r/100)第2层的价格是第1层价格再乘(1r/100)一步步递推下去就得到了指数公式。理解了这个递推关系你就明白为什么深度会直接影响价格也明白遍历树的时候必须记录每个节点所在的层数。我个人的习惯是先把公式在草稿纸上推一遍再写代码。尤其要注意r是百分数比如输入10表示10%代码里必须先做 r r / 100.0后面才能直接用(1r)参与计算。第一次写这道题时我忘了除100把10当成1.0去乘样例都过不了。这个坑几乎每届刷题的人都会踩一遍属于题目最容易让人忽视的细节。2.2 浮点精度与输出一位小数的正确姿势价格和销量都是实数销售额的累加必然涉及浮点运算。这里有三个必须死守的注意点。第一变量类型用double不要用float。float只有7位有效数字N一大的时候累加误差会逐步放大最后输出的一位小数可能差出1分钱。PAT评测对浮点误差的判断虽然有一定容忍度但用float去累加10万个double值实测确实会产生可感知的偏差WA的概率不低。保险起见凡是涉及价格、销售额的变量一律double。第二输出格式严格按题目要求来。题目要求保留一位小数那就用 printf(%.1lf\n, total)。printf的舍入规则在绝大多数情况下能满足题目对四舍五入的预期。有一点要注意C里直接用cout输出double默认精度不够你不设置setprecision的话可能只输出几位有效数字所以建议直接printf。第三pow函数的参数和返回值都是double深度depth通常是int直接 pow(1 r, depth) 没问题。如果树特别深比如退化成一条10万层的链反复调用pow也不会很慢但如果你心里对pow不踏实也可以在遍历时逐层乘每下探一层就把当前价格乘上(1r)。两种方式最后结果一致哪种顺手用哪种。3. 建图与遍历两版可直接AC的实现与关键注释3.1 用孩子列表存树而不是真去建二叉树建树这一步我见过有人试图把输入转换成二叉树结构去处理结果越搞越复杂。这道题的节点数量最大可以到10万孩子数量各不相同最直接、最不容易出错的方式是用“邻接表”的思路开一个 vector child[N] 的数组专门存每个节点的所有孩子编号。这么做的好处有三个。第一内存可控vector会按需扩容不需要提前猜每个节点有几个孩子。第二遍历时直接 for (int v : child[u]) 就能递归或入队代码非常自然。第三叶子节点的判断变成 child[u].empty()一行搞定比递归里额外传一个“是否有孩子”的布尔值要简洁得多。还需要一个数组存零售商的销量我通常命名为amount[]下标就是节点编号。注意这个数组只对叶子节点有意义内部节点的amount保持0遍历时也不会被访问到所以不用担心初始化的问题。如果你愿意也可以用结构体把“孩子列表”和“销量”包在一起但对这种题来说开两个数组已经够清楚没必要增加代码量。3.2 DFS递归版全代码拆解下面先给一版DFS递归实现适合思路比较直的人。整体结构就是从0号节点开始带着当前深度做深度优先遍历如果当前节点没有孩子说明是零售商计算销售额并累加如果还有孩子就逐个递归下去深度加一。#include cstdio #include vector #include cmath using namespace std; const int MAXN 100005; vectorint child[MAXN]; double amount[MAXN]; double total 0.0; void dfs(int u, int depth, double p, double r) { if (child[u].empty()) { total p * pow(1 r, depth) * amount[u]; return; } for (int v : child[u]) { dfs(v, depth 1, p, r); } } int main() { int n; double p, r; scanf(%d %lf %lf, n, p, r); r / 100.0; for (int i 0; i n; i) { int k; scanf(%d, k); if (k 0) { scanf(%lf, amount[i]); } else { for (int j 0; j k; j) { int v; scanf(%d, v); child[i].push_back(v); } } } dfs(0, 0, p, r); printf(%.1lf\n, total); return 0; }这段代码的核心就两个点。第一个是 main 里的读入分支Ki为0的时候读的是销量Ki大于0的时候读的是孩子编号。第二个是 dfs 里的叶子判断child[u].empty() 为真时当前节点就是零售商公式 p * pow(1 r, depth) * amount[u] 恰好完成“单价乘销量”的累加。需要注意的是递归深度等于树的层数。如果评测数据故意给了一条超长链也就是每个内部节点只有一个孩子递归层数可能达到10万层。某些评测环境的默认栈大小可能不太够表现为程序段错误或直接爆栈。我的建议是如果你能接受迭代写法优先用下面这版BFS彻底绕开递归爆栈问题如果你就想用DFS至少先确认环境没问题或者自己改写成显式栈的迭代DFS。3.3 BFS层序版实现与递归风险规避BFS版本是我更推荐的写法因为它不依赖函数调用栈内存可控而且层序天然适合计算深度。核心思路是用队列从根节点开始一层一层往外走每访问到一个节点先把它的孩子深度设为当前深度加1如果发现当前节点是叶子就立刻累加销售额。#include cstdio #include vector #include queue #include cmath using namespace std; const int MAXN 100005; vectorint child[MAXN]; double amount[MAXN]; int level[MAXN]; int main() { int n; double p, r; scanf(%d %lf %lf, n, p, r); r / 100.0; for (int i 0; i n; i) { int k; scanf(%d, k); if (k 0) { scanf(%lf, amount[i]); } else { for (int j 0; j k; j) { int v; scanf(%d, v); child[i].push_back(v); } } } queueint q; q.push(0); level[0] 0; double ans 0.0; while (!q.empty()) { int u q.front(); q.pop(); if (child[u].empty()) { ans p * pow(1 r, level[u]) * amount[u]; continue; } for (int v : child[u]) { level[v] level[u] 1; q.push(v); } } printf(%.1lf\n, ans); return 0; }BFS版本和DFS版本最大的不同在于DFS是带着深度参数递归进子节点BFS是先把节点编号入队再通过level数组记录每个节点的深度。level[0]默认是0正是根节点的深度。每次从队列取出节点u后把它的所有孩子深度都设置为 level[u] 1再入队。当某个节点没有孩子时它就是零售商直接按深度计算价格并累加。我实际测试下来BFS版的稳定性更高尤其在N比较大的时候不用担心递归栈空间的问题。而且这套代码改造成其他供应链题也非常方便把累加逻辑替换成最大值最小值统计即可后面第4章会详细说。4. 供应链题组一鱼三吃A1079与A1090、A1106的共骨架4.1 三道题的输入输出差异对照刷过PAT的人会发现Supply Chain不是一道题而是一组题。除了A1079 Total Sales of Supply Chain还有A1090 Highest Price in Supply Chain和A1106 Lowest Price in Supply Chain。它们三兄弟的输入格式完全一样都是N、P、r开头后面都是N行孩子列表或销量。真正不同的地方只有遍历时统计什么、输出什么。题目需要计算的内容遍历时的统计动作注意点A1079 Total Sales总销售额叶子节点销售额累加累加double保留1位小数A1090 Highest Price最高销售价格及其零售商数量找最大深度统计该深度的叶子数量只统计叶子输出注意小数位A1106 Lowest Price最低销售价格及其零售商数量找最小深度统计该深度的叶子数量深度从0开始别漏根节点理解它们之间的关系之后你会发现这三道题其实是同一棵树上换了三种不同的“统计目标”。A1079要把每个叶子的价格乘销量再加起来A1090和A1106则只要看深度因为价格是深度的单调函数r不小于0时越深价格越高。所以求最高价就是找最大深度求最低价就是找最小深度。4.2 换目标函数时最容易改错的地方从A1079切到A1090或A1106时最容易犯的错有两个。第一个错误是忘记“只统计叶子”。最高价格和最低价格都必须落在零售商身上也就是叶子节点。如果你在遍历过程中顺便对内部节点也做了深度比较很可能得到一个错误的极值因为内部节点可能恰好处在更深或更浅的位置但它不出售商品没有终端售价一说。所以比较深度的代码必须写在 child[u].empty() 的分支里。第二个错误是混淆统计目标。A1090要的是最高价格对应的零售商数量不是所有零售商的数量。有些人写着写着就变成统计全部叶子数量了样例可能碰巧对数据一大就挂。建议写代码前先想清楚你维护的变量是“最大深度”还是“最大深度对应的叶子个数”。A1106同理它要最小深度对应的叶子个数。再提醒一个细节这三道题虽然共用建树代码和遍历框架但输出的小数位数不一样有的要求一位小数有的要求两位甚至四位。千万别把A1079的“%.1lf”直接复制到其他题上真要这么干错得毫无悬念。刷题最忌讳的就是“代码能跑就不管了”提交之前一定再把题目输出要求读一遍。5. 刷题时真实踩过的坑和针对性测试用例5.1 根节点就是零售商时别让边界条件溜走有一种极端但完全合法的输入整条供应链只有一个节点它既是根供应商又是零售商。输入1 100.0 10.0 0 5唯一的零售商就是0号节点深度为0销售单价就是初始价格100总销售额是100×5500输出“500.0”。这个场景看似简单却能拦住不少人。原因是一些人在DFS的递归入口里想当然地认为“root肯定有孩子”于是把叶子判断放在了递归子节点的循环里导致根节点直接没有被处理。我自己写过一版代码main函数里单独把根节点入队后又额外判断了“如果有孩子就走循环”的逻辑结果根节点恰好没有孩子时整个统计被跳过输出一个0.0。正确的做法其实很简单遍历逻辑对每个节点一视同仁先判断叶子再处理孩子。把根节点也当成普通节点对待这个坑就不存在了。5.2 输入规模大时IO和栈都可能成为隐形杀手N最大能到10万这意味着输入行很多孩子编号也很多。如果你用cin去读又不关同步可能被IO卡到超时。我建议直接用scanf读全部输入或者用下面这段经典优化ios::sync_with_stdio(false); cin.tie(nullptr);之前做某道数据量大的模拟题时我用cin没关同步本地跑起来只觉得慢一点提交上去直接TLE关掉之后瞬间通过。供应链这组题虽然不是最极端的IO卡时间题但养成读入格式都用scanf的习惯能省掉很多莫名其妙的问题。还有栈的问题。用递归DFS时如果评测数据里出现一条很深的链栈压力会非常大。我印象里有些递归写法在链状数据上多次出现段错误后来统一改成BFS或者显式栈迭代DFS就再也没遇到过这类问题。所以如果你在练习时发现DFS递归版本提交不稳定不要怀疑算法思路大概率就是栈空间的问题直接换BFS版本即可。5.3 手工验证样例从一次性通过到确认正确性刷题不能只看题目给的原样样例过了就收工。供应链这组题的场景和数据边界都比较清晰我一般会准备三个用例快速自测。第一个用例就是前面说的单节点场景验证根为叶子时逻辑是否正确。第二个用例是两三层的小树带上不同深度、不同销量的叶子手工算出结果后对答案。第三个用例是一条链状树比如N等于1000每个内部节点只有一个孩子专门验证遍历会不会爆栈、会不会超时。算这些用例时可以用最简单的思路把树画出来标上每个叶子的深度和价格逐项相乘再累加。用前面那个三节点的例子再走一遍0号两个孩子1和21号和2号都是叶子深度都是1单价110销量分别是10和2总销售额1320。把这段输入喂给BFS代码输出应该是“1320.0”。这类自测用例虽然简单但能逼你把建树、深度、累加整条链路走通。真要遇到WA再回头检查公式里r有没有除100、float是不是写成double、叶子判断有没有漏基本就能定位到问题。最后再分享一个小技巧写这组供应链题的时候我习惯把建树部分单独封装成一个函数遍历逻辑单独封一个函数不同题目之间只需要替换统计逻辑。这套模板在A1079、A1090、A1106之间反复用了很多次每次迁移都很省事。如果你正在密集刷PAT的树型题目建议也维护一套自己的“建树遍历”模板多题复用时收益很大。