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

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

6天前

一、题目解读

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

二、解题思路

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

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

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

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

三、解题步骤

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

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

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

4. 拓扑排序迭代：

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

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

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

四、代码与注释

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 定义神经元结构体
struct Neuron {
    int c;      // 当前状态
    int u;      // 阈值
    int in_degree;  // 入度
    bool is_output; // 是否为输出层神经元
};

int main() {
    int n, p;
    cin >> n >> p;
    
    vector<Neuron> neurons(n+1); // 神经元数组，从1开始编号
    vector<vector<pair<int, int>>> adj(n+1); // 邻接表，存储边和权重
    
    // 输入神经元初始状态和阈值
    for (int i = 1; i <= n; ++i) {
        cin >> neurons[i].c >> neurons[i].u;
        neurons[i].is_output = true; // 初始假设所有神经元都是输出层
    }
    
    // 输入边信息并构建邻接表
    for (int i = 0; i < p; ++i) {
        int from, to, w;
        cin >> from >> to >> w;
        adj[from].emplace_back(to, w);
        neurons[to].in_degree++; // 目标节点入度增加
        neurons[from].is_output = false; // 有出边的节点不是输出层
    }
    
    // 拓扑排序队列，初始化时加入所有入度为0的节点
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (neurons[i].in_degree == 0) {
            q.push(i);
        } else {
            // 非输入层神经元需要减去阈值
            neurons[i].c -= neurons[i].u;
        }
    }
    
    // 拓扑排序处理
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        // 如果当前神经元状态<=0，不传递信号
        if (neurons[current].c <= 0) {
            for (auto &edge : adj[current]) {
                int next = edge.first;
                if (--neurons[next].in_degree == 0) {
                    q.push(next);
                }
            }
            continue;
        }
        
        // 向所有邻接神经元传递信号
        for (auto &edge : adj[current]) {
            int next = edge.first;
            int weight = edge.second;
            neurons[next].c += weight * neurons[current].c;
            
            // 入度减为0时加入队列
            if (--neurons[next].in_degree == 0) {
                q.push(next);
            }
        }
    }
    
    // 收集输出层神经元结果
    bool has_output = false;
    for (int i = 1; i <= n; ++i) {
        if (neurons[i].is_output && neurons[i].c > 0) {
            cout << i << " " << neurons[i].c << endl;
            has_output = true;
        }
    }
    
    if (!has_output) {
        cout << "NULL" << endl;
    }
    
    return 0;
}