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

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

2个月前 (07-11)

【NOIP提高组2003】神经网络(洛谷P1038)题解:拓扑排序与动态规划的应用 NOIP提高组  拓扑排序 动态规划 第1张

一、题目解读

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

五、总结

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

原创内容 转载请注明出处

分享给朋友:

相关文章

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

一、题目解读题目要求在一个n×m的网格中,从左上角到右下角选择一条路径,路径上的数字可重复取用,求取数之和的最大值。路径限制为仅能向右或向下移动。需注意路径的灵活性与重复取数的可能性,传统单向动态规划...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

2017年 NOIP 提高组 逛公园(洛谷P3953)题解:代码解析与优化

2017年 NOIP 提高组 逛公园(洛谷P3953)题解:代码解析与优化

一、题目解读    2017年NOIP提高组“逛公园”题目(洛谷P3953)要求在有向图中计算从起点到终点满足特定条件的路径数量。题目难点在于处理路径长度限制与...

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

一、题目解读牛客25461题要求计算一个花园中n朵花到两个喷泉的最小距离平方和。用户需输入喷泉坐标(x1,y1)和(x2,y2),以及n朵花的坐标(x,y),通过合理分配每朵花到两个喷泉的距离,使总距...

LeetCode 2222题解析:高效统计"010"与"101"子序列数量的算法优化

LeetCode 2222题解析:高效统计"010"与"101"子序列数量的算法优化

一、题目解读题目要求计算给定字符串中包含"010"或"101"子序列的数量。关键难点在于高效遍历所有子序列,避免重复计算。传统暴力解法时间复杂度O(n^3)会超...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。