2003年NOIP提高组神经网络（洛谷P1038）：拓扑排序在生物神经网络中的应用
一. 问题理解
这道题目模拟了一个简化的生物神经网络模型。我们需要理解几个关键概念：
神经元：网络中的基本单元，每个神经元有当前状态(C)和阈值(U)
兴奋状态：当C > 0时，神经元处于兴奋状态，会向连接的神经元传递信号
层级结构：网络分为输入层、中间层和输出层，信息只能从输入层流向输出层
二. 算法选择
这个问题适合使用拓扑排序算法来解决，原因如下：
三. 实现解析
让我们分解代码的关键部分：
数据结构设计：
初始化阶段：
读取神经元初始状态和阈值
构建邻接表时，同时更新目标神经元的入度
标记有出边的神经元为非输出层
拓扑排序处理：
初始化队列时加入所有入度为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;
}六. 学习价值
通过这道题目，我们可以学习：
如何将实际问题抽象为图论模型
拓扑排序的应用场景
生物神经网络的基本原理
如何设计合适的数据结构来解决问题
七. 扩展思考
如果网络中存在环会怎样？如何检测？
如何优化算法以处理更大规模的网络？
如何修改模型使其更接近真实的生物神经网络？
这道题目很好地结合了图论和生物神经网络的知识，通过代码实现加深了对这两个领域的理解。
原创内容 转载请注明出处
