2003年NOIP提高组神经网络（洛谷P1038）：拓扑排序在生物神经网络中的应用

2天前比赛题解47

一. 问题理解

这道题目模拟了一个简化的生物神经网络模型。我们需要理解几个关键概念：

‌神经元‌：网络中的基本单元，每个神经元有当前状态(C)和阈值(U)
‌兴奋状态‌：当C > 0时，神经元处于兴奋状态，会向连接的神经元传递信号
‌层级结构‌：网络分为输入层、中间层和输出层，信息只能从输入层流向输出层

二. 算法选择

这个问题适合使用‌拓扑排序‌算法来解决，原因如下：

神经网络是一个有向无环图(DAG)，信息流动有明确方向
我们需要按照神经元之间的依赖关系依次计算状态
拓扑排序能保证在处理每个神经元时，所有输入它的神经元都已被处理

三. 实现解析

让我们分解代码的关键部分：

‌数据结构设计‌：

使用结构体Neuron存储每个神经元的状态、阈值、入度和是否为输出层
邻接表adj存储图的连接关系，记录每个神经元指向的神经元及连接权重

‌初始化阶段‌：

读取神经元初始状态和阈值
构建邻接表时，同时更新目标神经元的入度
标记有出边的神经元为非输出层

‌拓扑排序处理‌：

初始化队列时加入所有入度为0的神经元（输入层）
对于每个处理的神经元：

如果状态≤0，不传递信号，仅减少邻接神经元入度
如果状态>0，计算对邻接神经元的影响

邻接神经元入度减为0时加入队列

‌输出处理‌：

遍历所有神经元，输出状态>0的输出层神经元
如果没有符合条件的输出，输出"NULL"

四. 关键点说明

‌阈值处理‌：非输入层神经元初始状态为0，需要先减去阈值U
‌信号传递‌：只有当神经元兴奋(C>0)时才传递信号
‌拓扑顺序‌：确保每个神经元在被处理前，所有输入信号都已计算完成

五. 完整代码

#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;
}