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

ftggdnt

一、题目解读

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题解