企业官网建设流程全解析

提到 P1038，很多打 OI 的老玩家都会心一笑。这是 NOIP 2003 提高组的第一题，名字叫“神经网络”，听起来像是要去搞深度学习，实际上它是一道非常标准的图论递推题。题目给你一个带权有向无环图，每个节点有状态 C 和阈值 U，边上有传递权重 W，信号从入度为 0 的节点出发，沿着边一层层往后传，最终在出度为 0 的节点上输出结果。我第一次刷到这道题时，花了不少时间才把那个又像公式又像定义的说明搞清楚，后来带新人时发现，大部分人栽跟头的地方也都集中在理解题意和边界处理上。这篇文章就把我踩过的坑和总结出的经验完整写出来，适合刚学拓扑排序的选手，也适合想快速过一遍经典题的复习者。

1. 剥掉“神经网络”的外壳：题目在算什么

1.1 一个带权有向无环图上的信号传递

题目虽然叫神经网络，但剥掉这层壳之后，剩下的东西非常朴素：一张有向无环图，节点编号从 1 到 n，边上带一个整数权值。每个节点有两个属性，一个是状态 C，一个是阈值 U。信号传播规则是这样：对于某个节点 i，先算出它的“输出信号” C_i - U_i，如果这个值大于 0，说明节点处于兴奋状态，它会沿着每一条出边把信号传出去，传给后继节点 j 的信号强度是 (C_i - U_i) 乘以边权 W。

后一个节点会把自己从所有前驱那里收到的信号累加起来，作为自己的状态 C。注意，节点 j 自己的阈值 U_j 并不会直接参与累加，只有当节点 j 作为前驱向它的后继传播时，才需要用到 U_j。这个逻辑很像开会传话：只有嗓门大过房间底噪的人才能发言，发言音量是“自己的嗓门减掉底噪”，而坐在后面的人听到的总音量是所有人发言音量乘上“亲密度”后的总和。房间底噪就是阈值，亲密度就是边权。

这里的关键是，方向不能搞反。很多初学者会写成“当前节点 C - 后继节点 U”，或者把阈值当成累加时要减掉的东西，结果一跑样例就错。神经网络这个包装容易让人联想，但模型本质就是图上的递推：每个节点的最终状态只依赖它的前驱传入的信号，而信号是否传得出去，只看当前节点自己的输出是否为正。

1.2 状态、阈值与输出信号的关系

输入层、中间层、输出层的定义也要先理清楚。入度为 0 的节点是输入层，它们的状态 C 由外部直接给定，不需要通过接收前驱信号来获得。除输入层外的所有节点，初始状态 C 一律为 0，之后靠前驱传来的信号累加。出度为 0 的节点是输出层，题目要求最后把输出层里状态 C 大于 0 的节点编号和 C 值打印出来。

有一个容易忽略的点：题目读入时会给每个节点都输入一组 C 和 U，但输入层之外的 C 即使给了一个非零值，也必须改成 0。如果顺手把读进来的 C 直接当成初始状态，中间层就可能凭空多出一些信号，导致整条传播链错得离谱。U 则不受影响，每个节点都有自己的固定阈值，读入后保留即可。

还有一层理解要到位：所谓状态 C 是动态变化的。输入层节点的 C 不靠累加，直接由外部注入；中间层节点的 C 是多个前驱贡献的总和；输出层节点的 C 也是累加出来的。当某个节点作为前驱去传播时，使用的输出信号是“它自己的最终 C 减它自己的 U”，这个最终 C 必须是在接收完所有前驱贡献之后的值，这就自然引出了拓扑排序。

2. 拓扑排序是唯一正解：状态怎么一层层推下去

2.1 为什么必须按拓扑序计算

题目给出的图是有向无环图，这一点非常关键。正因为没有环，才存在拓扑序，我们才能按照拓扑序从输入层向输出层逐层推进。为什么不能随便按节点编号顺序扫一遍？因为一个节点在收到全部前驱信号之前，它的 C 值是不完整的。如果你在处理节点 5 的时候，前驱节点 3 还没处理完，那么节点 5 收到的信号就会少一份，后续的计算自然全部错误。

拓扑排序保证了这样一个性质：当一个节点从队列中弹出时，它的所有前驱都已经处理完毕，所有该传给它的信号都已经累加到它的 C 上。这就像上课前必须等所有先修课都学完，才能开始学这门课。动态规划里叫“无后效性”，在图上我们直接用拓扑序模拟依赖关系。

还有一种特殊情况需要说明：有些节点可能在拓扑序中并不属于“一层一层”的结构，而是多个节点并行依赖。比如节点 A 和 B 都指向 C，而 A 和 B 之间没有依赖，那么 A 和 B 谁先出队都行。Kahn 算法用队列处理这种并行关系非常自然，队列里可以同时存在多个入度为 0 的节点，它们的处理顺序不影响结果。

2.2 图的存储与入度出度的统计

我习惯用邻接表存储出边，结构是 vector<pair<int, long long>> g[N]。这里 pair 的 first 是后继节点编号，second 是边权。同时维护两个数组：indeg 表示入度，outdeg 表示出度。为什么要同时维护入度和出度？入度用来判断节点是不是输入层，也用于拓扑排序的入队判断；出度用来判断节点是不是输出层，最后输出时用。

读入每一条有向边 a->b，权值为 w 时，要做三件事：

g[a].push_back({b, w}); indeg[b]++; outdeg[a]++;

这里有个细节：输入的节点编号从 1 开始，数组也最好从 1 开始使用，不要留 0 下标，避免后面输出时还得做偏移。邻接表只存出边就够用了，因为信号传播是当前节点往后继方向走，更新后继状态只需要知道当前节点的所有出边；不需要知道前驱边，因为前驱的贡献早在当前节点入队前就已经累加完毕了。

入度数组在拓扑排序中的另一个用途是“动态清零”。每处理完一个前驱节点，就把后继节点的入度减 1，当入度减到 0 时，说明这个后继的所有前驱都已经处理完，它当前接收到的 C 就是完整状态，可以入队了。这个动态清零的过程比一开始就记录一个固定的拓扑序数组更直观，也不需要额外判重。

2.3 递推公式的完整表述

核心更新逻辑可以写成这样：

if (c[cur] - u[cur] > 0) { long long signal = c[cur] - u[cur]; for (auto e : g[cur]) { int to = e.first; long long w = e.second; c[to] += signal * w; } } for (auto e : g[cur]) { int to = e.first; if (--indeg[to] == 0) q.push(to); }

这里把“更新信号”和“维护拓扑序”分成两个循环，逻辑更清晰。第一个循环只在当前节点兴奋时才执行；第二个循环无论当前节点是否兴奋都一定要执行。为什么？因为即使节点不传递信号，它在拓扑序中仍然是后继节点的前驱，必须让后继的入度减 1，否则队列永远不会把后继加进来。

当然也可以把两个逻辑合并成一个循环：

for (auto e : g[cur]) { if (c[cur] - u[cur] > 0) c[e.first] += (c[cur] - u[cur]) * e.second; if (--indeg[e.first] == 0) q.push(e.first); }

这样写代码更短，但初学者容易把第二个 if 误写进兴奋条件里，导致不兴奋的节点不维护入度。所以我更建议先写清晰的两个循环，等完全理解了再合并也不迟。

计算 signal 时，记得先存成一个变量，不要在每条出边里重复计算 c[cur] - u[cur]。虽然多次计算不算错，但会让代码显得啰嗦，而且一旦后面要修改公式，容易漏改。另外，signal 的类型用 long long，因为状态和边权的乘积可能会超过 32 位整数范围。

3. 完整实现：一份能直接 AC 的代码

3.1 核心代码（C++ 版）

直接给一份可以运行的完整代码，注释也写得比较细，方便对照上面的讲解来理解。

#include <bits/stdc++.h> using namespace std; const int MAXN = 105; int n, p; long long c[MAXN], u[MAXN]; int indeg[MAXN], outdeg[MAXN]; vector<pair<int, long long>> g[MAXN]; int main() { scanf("%d%d", &n, &p); for (int i = 1; i <= n; i++) { scanf("%lld%lld", &c[i], &u[i]); } for (int i = 0; i < p; i++) { int a, b; long long w; scanf("%d%d%lld", &a, &b, &w); g[a].push_back({b, w}); indeg[b]++; outdeg[a]++; } // 除输入层外，其他节点的初始状态必须为 0 for (int i = 1; i <= n; i++) { if (indeg[i] > 0) c[i] = 0; } queue<int> q; for (int i = 1; i <= n; i++) { if (indeg[i] == 0) q.push(i); } while (!q.empty()) { int cur = q.front(); q.pop(); if (c[cur] - u[cur] > 0) { long long signal = c[cur] - u[cur]; for (auto e : g[cur]) { int to = e.first; long long w = e.second; c[to] += signal * w; } } for (auto e : g[cur]) { int to = e.first; indeg[to]--; if (indeg[to] == 0) q.push(to); } } bool hasOutput = false; for (int i = 1; i <= n; i++) { if (outdeg[i] == 0 && c[i] > 0) { printf("%d %lld\n", i, c[i]); hasOutput = true; } } if (!hasOutput) printf("NULL\n"); return 0; }

这段代码在绝大多数评测环境下可以直接通过。主逻辑只有二十多行，关键就是两个循环：一个负责传播信号，一个负责维护拓扑序。

3.2 代码里几个容易写错的地方

第一个容易错的地方是在读入完所有边之后，忘记把非输入层的 c 清零。输入数据里并不保证非输入层的 c 为 0，所以必须加一个循环做重置。我见过有人写的是“读入时如果 indeg[i] > 0 就把 c[i] = 0”，这会有问题，因为边还没读入完，indeg 还没统计好，根本不知道哪些节点是输入层。

第二个容易错的地方是输出层的判断。出度为 0 的节点才算输出层，但出度为 0 的节点有可能是孤立点？题目应该不会出现孤立点，但即便有，按规则它也是输入层和输出层同体。判断条件用 outdeg[i] == 0，然后看 c[i] > 0，这两者必须同时满足。只判断 c[i] > 0 会把中间层也输出，只判断出度为 0 会把不兴奋的输出层也输出，都是错的。

第三个容易错的地方是扫描输出层时，有人会在循环里用if (outdeg[i] == 0 && c[i] > 0)输出了，然后后面又加一个else printf("NULL\n")，这样每个不满足条件的节点都会打一个 NULL，显然不对。正确做法是记录 hasOutput，全部扫描完后再判断。

3.3 复杂度与数据范围

时间复杂度是 O(n + p)，n 是节点数，p 是边数。每个节点入队一次、出队一次，每条边在传播和维护入度时各遍历一次，所以总操作次数和点数边数成正比。空间复杂度也是 O(n + p)，主要是邻接表存储边的开销。

这道题节点数一般不大，但边权、状态值的绝对值可能比较大，乘积可能超过 int 范围。所以代码里我全部用了 long long。如果题目数据范围很小，用 int 也能过，但养成用 long long 的习惯可以避免很多不必要的数据溢出问题。尤其在竞赛里，很多题目不会故意卡 long long，但用 int 一旦出错就是致命 WA。

输入输出方面，用 scanf/printf 或者关闭同步的 cin/cout 都可以。P1038 数据量不大，即使用朴素 cin/cout 也能过，但竞赛里推荐保留 scanf/printf，省心又稳定。

4. 新手最容易翻车的几个细节

4.1 阈值扣减的位置搞错

这是这道题最经典的一个坑。传播规则是：节点 i 的输出信号为 C_i - U_i，当它大于 0 时，信号强度为 C_i - U_i，然后乘上边权传给后继。因此累加时要写成c[to] += (c[cur] - u[cur]) * w。但很多人会错误地写成c[to] += c[cur] * w，完全忽略了阈值，还有人在计算后继时把后继的阈值减掉，写成c[to] = (c[to] + signal) - u[to]，这更是错得离谱。

要理解为什么不减后继阈值：后继节点的 C 表示它接收到的总信号强度，这个强度值在它作为前驱向外传播时才会和它自己的阈值比较。阈值是每个节点的“兴奋门槛”，它在接收阶段只是一个待比较的固定值，不会参与累加。类比一下，房间底噪只影响你能不能发言，不影响你听到别人说话的响度。

4.2 非输入层的初始状态覆盖晚了

再强调一次覆盖问题。正确顺序是：先读入所有 C 和 U，再读入所有边，统计完入度后，将indeg[i] > 0的 c[i] 置为 0。有些题目数据友好，非输入层的 C 本来就给的是 0，所以有人不清零也能 AC，但这不是通用做法，换一组数据就会挂。

覆盖操作必须在读完边之后进行，因为统计入度需要边信息。如果你在读 C 和 U 的时候判断“这个点有没有边指向它”，此时入度数组还没更新完，判断必然不准。这是一个顺序问题，也是一个典型的“读题不仔细”导致的问题。

4.3 不兴奋的节点也要参与拓扑排序

我在带新人时经常看到这种错误：只在节点兴奋时才遍历出边，不兴奋就不遍历，结果后续节点的入度永远减不到 0，队列提前为空，程序直接结束，什么也不输出。为什么会这样？因为他们把“信号传播”和“拓扑排序维护”混为一谈，以为只有传递信号的边才需要处理入度。

实际上，拓扑排序维护的是一个纯粹依赖关系，与节点是否兴奋无关。只要存在边 cur -> to，cur 就是 to 的前驱，cur 处理完就必须让 to 的入度减 1。哪怕 cur 已经“死掉”，它仍然在依赖关系中占一个位置。所以一定要保证出边遍历在任何情况下都执行。你可以分开写两个循环，也可以在同一个循环里保证第二个 if 不受兴奋条件控制。

4.4 输出“NULL”的时机

输出层中如果没有任何一个节点的状态 C 大于 0，就输出一行大写的 NULL。注意是字符串NULL，不是数字 0，也不是null。之前有人卡在这儿，样例输出只有数字，他自己写程序没输出任何东西，但评测要求必须有输出，所以补上 NULL 才过。

输出顺序要按节点编号从小到大。因为最后扫描时 for 循环是从 1 到 n，天然满足这个要求。多组数据的情况这里不存在，但依然建议每组输出换行。最后，如果 hasOutput 为 true，就不要再输出 NULL，否则多了一行反而错。

5. 从这道题延伸出去的东西

5.1 这类 DAG 状态递推还能用在哪

P1038 本质上是一种“DAG 上按拓扑序递推状态”的模型，这种模型在算法题里太常见了。比如很多求最长路径的题目，在有向无环图上可以拓扑排序后递推dp[v] = max(dp[v], dp[u] + w)；再比如“关键路径”问题、动态规划中依赖有向无环图的状态压缩、甚至部分概率 DP，底层逻辑都是“前驱状态确定后，才能推后继状态”。

学会这一题，相当于学会了这类问题的标准套路：建图，统计入度，队列拓扑，出队时做 DP 或状态更新，最后在出度为 0 或特定节点上收集答案。很多看起来复杂的题，只要意识到它是一张 DAG，就可以用同样的骨架去套。

5.2 面对陌生题名怎么快速拆解

这道题叫“神经网络”，名字充满欺骗性。竞赛题经常这样包装，把简单的图论、数学、字符串问题藏在生物学、物理、社交网络这些概念背后。拿到一道题，第一步不是背代码，而是抓三个东西：有哪些实体，实体之间什么关系，状态怎么转移。在这道题里，实体是节点和边，关系是前驱后继，转移是 C 值通过边权累加。抓住这三点，名字再唬人也不怕。

我个人有一个习惯：做题时先把题面里所有名词翻译成自己熟悉的算法语言。比如“神经元”就是节点，“阈值”就是判断条件，“兴奋”就是状态值大于阈值，“突触权值”就是边权。翻译完基本就知道该用什么算法了。P1038 翻译完就是一个拓扑排序，剩下的只是细节。

5.3 关于这道题的最后一点经验

最后说个我自己当初踩过的坑，就是输出 NULL 的那道坎。当时我以为没有兴奋的输出层节点时，程序什么都不输出就能交给评测系统处理，结果连续 WA 了好几次。后来才认认真真把题目最后一段看完，才发现有明确的 NULL 要求。从那以后，凡是有“如果没有任何结果输出某个字符串”这种要求，我都会在写代码之前先在注释里标出来，绝不等到写完再想。

另外一个心得是：这种经典题虽然简单，但非常值得反复刷。因为题面里的文字陷阱、边界条件、数据类型问题，都是真实比赛里最容易丢分的地方。能在这种题上一遍 AC，说明你的读题能力、图论基础和细节控制都过关了；假如连这种题都需要反复调试，那后面的大题只会更痛苦。把这题的每个细节吃透，后面的路会好走很多。