【NOIP提高组2003】神经网络（洛谷P1038）题解：拓扑排序与动态规划的应用

fiwhgikbl

一、题目解读

2003年NOIP提高组中的“神经网络”题目（洛谷P1038）要求处理一个由神经元和带权有向边构成的网络。题目给定神经元的初始状态、阈值，以及神经元之间的连接关系，需要模拟信号传递过程，并输出最终状态。核心在于解决信号传递的顺序和条件判断，涉及到图论算法的应用。

二、解题思路

采用拓扑排序为核心思路，将神经网络抽象为有向无环图（DAG）。关键在于处理节点的入度和状态更新：

1. 利用拓扑排序确定节点处理顺序，保证每个节点仅在其所有前驱节点处理后被访问；

2. 通过邻接表存储边信息，动态维护节点的入度和状态；

3. 节点传递信号的条件是其状态大于阈值，且传递权重影响后续节点状态。

三、解题步骤

1. 数据输入与初始化：读入神经元数量n、边数p，初始化神经元状态、阈值及邻接表；

2. 构建图结构：根据边信息更新入度，标记输出层节点；

3. 拓扑排序预处理：将入度为0的节点加入队列，并调整非输入层节点状态（减去阈值）；

4. 拓扑排序迭代：

○ 弹出队首节点，若状态≤0则不传递信号；

○ 否则向邻接点传递信号（状态加权更新），并递减其入度，若入度为0则加入队列；

5. 输出结果：最终状态即为输出层节点的状态。

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. using namespace std;
   
5. 
   
6. // 定义神经元结构体
   
7. struct Neuron {
   
8. int c; // 当前状态
   
9. int u; // 阈值
   
10. int in_degree; // 入度
    
11. bool is_output; // 是否为输出层神经元
    
12. };
    
13. 
    
14. int main() {
    
15. int n, p;
    
16. cin >> n >> p;
    
17. 
    
18. vector<Neuron> neurons(n+1); // 神经元数组，从1开始编号
    
19. vector<vector<pair<int, int>>> adj(n+1); // 邻接表，存储边和权重
    
20. 
    
21. // 输入神经元初始状态和阈值
    
22. for (int i = 1; i <= n; ++i) {
    
23. cin >> neurons[i].c >> neurons[i].u;
    
24. neurons[i].is_output = true; // 初始假设所有神经元都是输出层
    
25. }
    
26. 
    
27. // 输入边信息并构建邻接表
    
28. for (int i = 0; i < p; ++i) {
    
29. int from, to, w;
    
30. cin >> from >> to >> w;
    
31. adj[from].emplace_back(to, w);
    
32. neurons[to].in_degree++; // 目标节点入度增加
    
33. neurons[from].is_output = false; // 有出边的节点不是输出层
    
34. }
    
35. 
    
36. // 拓扑排序队列，初始化时加入所有入度为0的节点
    
37. queue<int> q;
    
38. for (int i = 1; i <= n; ++i) {
    
39. if (neurons[i].in_degree == 0) {
    
40. q.push(i);
    
41. } else {
    
42. // 非输入层神经元需要减去阈值
    
43. neurons[i].c -= neurons[i].u;
    
44. }
    
45. }
    
46. 
    
47. // 拓扑排序处理
    
48. while (!q.empty()) {
    
49. int current = q.front();
    
50. q.pop();
    
51. 
    
52. // 如果当前神经元状态<=0，不传递信号
    
53. if (neurons[current].c <= 0) {
    
54. for (auto &edge : adj[current]) {
    
55. int next = edge.first;
    
56. if (--neurons[next].in_degree == 0) {
    
57. q.push(next);
    
58. }
    
59. }
    
60. continue;
    
61. }
    
62. 
    
63. // 向所有邻接神经元传递信号
    
64. for (auto &edge : adj[current]) {
    
65. int next = edge.first;
    
66. int weight = edge.second;
    
67. neurons[next].c += weight * neurons[current].c;
    
68. 
    
69. // 入度减为0时加入队列
    
70. if (--neurons[next].in_degree == 0) {
    
71. q.push(next);
    
72. }
    
73. }
    
74. }
    
75. 
    
76. // 收集输出层神经元结果
    
77. bool has_output = false;
    
78. for (int i = 1; i <= n; ++i) {
    
79. if (neurons[i].is_output && neurons[i].c > 0) {
    
80. cout << i << " " << neurons[i].c << endl;
    
81. has_output = true;
    
82. }
    
83. }
    
84. 
    
85. if (!has_output) {
    
86. cout << "NULL" << endl;
    
87. }
    
88. 
    
89. return 0;
    
90. }

复制代码

五、总结

该解法巧妙将神经网络转化为拓扑排序问题，通过动态规划思想维护节点状态，避免了复杂的递归或深度优先搜索。关键在于利用入度控制节点处理顺序，确保信号传递的正确性。代码简洁高效，是解决此类图论问题的经典范例。

来源：CSP题解