AcWing 477:神经网络 ← 拓扑排序+链式前向星

【题目来源】
https://www.acwing.com/problem/content/479/

【题目描述】
人工神经网络(Artificial Neural Network)是一种新兴的具有自我学习能力的计算系统,在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。
对神经网络的研究一直是当今的热门方向,兰兰同学在自学了一本神经网络的入门书籍后,提出了一个简化模型,他希望你能帮助他用程序检验这个神经网络模型的实用性。
在兰兰的模型中,神经网络就是一张有向图,图中的节点称为神经元,而且两个神经元之间至多有一条边相连,下图是一个神经元的例子:

图中,X1—X3是信息输入渠道,Y1-Y2 是信息输出渠道,C1 表示神经元目前的状态,Ui 是阈值,可视为神经元的一个内在参数。 
神经元按一定的顺序排列,构成整个神经网络。
在兰兰的模型之中,神经网络中的神经元分为几层;称为输入层、输出层,和若干个中间层。
每层神经元只向下一层的神经元输出信息,只从上一层神经元接受信息。
下图是一个简单的三层神经网络的例子。

兰兰规定,Ci 服从公式:C_i=\sum W_{ji}C_j-U_i,(其中 n 是网络中所有神经元的数目)
公式中的Wji(可能为负值)表示连接 j 号神经元和 i 号神经元的边的权值。
当 Ci 大于 0 时,该神经元处于兴奋状态,否则就处于平静状态。
当神经元处于兴奋状态时,下一秒它会向其他神经元传送信号,信号的强度为 Ci。
如此.在输入层神经元被激发之后,整个网络系统就在信息传输的推动下进行运作。
现在,给定一个神经网络,及当前输入层神经元的状态(Ci),要求你的程序运算出最后网络输出层的状态。

【输入格式】
输入文件第一行是两个整数 n 和 p。
接下来 n 行,每行两个整数,第 i+1 行是神经元 i 最初状态和其阈值(Ui)。注意:输入层给定的状态即为最终值,不需要再减去 Ui,非输入层的神经元开始时状态必然为 0。
再下面 P 行,每行有两个整数 i,j 及一个整数 Wij,表示连接神经元 i、j 的边权值为 Wij。

【输出格式】
输出文件包含若干行,每行有两个整数,分别对应一个神经元的编号,及其最后的状态,两个整数间以空格分隔。
仅输出最后状态大于零的输出层神经元状态,并且按照编号由小到大顺序输出。
若输出层的神经元最后状态都不大于零,则输出 NULL。

【数据范围】
1≤n≤100

【输入样例】
5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1

【输出样例】
3 1
4 1
5 1

【算法分析】
● 拓扑序列:https://blog.csdn.net/hnjzsyjyj/article/details/129811447

● 链式前向星:https://blog.csdn.net/hnjzsyjyj/article/details/139369904
val[idx]:存储编号为 idx 的边的值
e[idx]:存储编号为 idx 的结点的值
ne[idx]:存储编号为 idx 的结点指向的结点的编号
h[a]:存储头结点 a 指向的结点的编号

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=105;
const int maxm=maxn*maxn/2;
int val[maxm],e[maxn],ne[maxn],h[maxn],idx;
int f[maxn],u[maxn],din[maxn],dout[maxn];
int q[maxn];
int n,m;void add(int a,int b,int w) {val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void topsort() {int hh=0, tt=-1;for(int i=1; i<=n; i++)if(!din[i]) q[++tt]=i;while(hh<=tt) {int t=q[hh++];for(int i=h[t]; i!=-1; i=ne[i]) {int j=e[i];if(--din[j]==0) q[++tt]=j;}}
}int main() {cin>>n>>m;for(int i=1; i<=n; i++) {cin>>f[i]>>u[i];if(!f[i]) f[i]-=u[i];}memset(h,-1,sizeof h);while(m--) {int a,b,c;cin>>a>>b>>c;add(a,b,c);dout[a]++;din[b]++;}topsort();for(int i=0; i<n; i++) {int j=q[i];if(f[j]>0) {for(int k=h[j]; k!=-1; k=ne[k])f[e[k]]+=f[j]*val[k];}}bool flag=true;for(int i=1; i<=n; i++)if(!dout[i] && f[i]>0) {cout<<i<<" "<<f[i]<<endl;flag=false;}if(flag) cout<<"NULL"<<endl;return 0;
}/*
in:
5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1out:
3 1
4 1
5 1
*/




【参考文献】
https://www.acwing.com/solution/content/3706/
https://blog.csdn.net/hnjzsyjyj/article/details/139369904
https://blog.csdn.net/hnjzsyjyj/article/details/129811447




 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/348892.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

致 粉丝de信

致 粉丝 -本文呢看不下去别看&#xff0c;但是学业是真的重要&#xff08;平常有信奥&#x1f62b;&#xff09;&#xff0c;电脑没收……更新可能得到暑假&#xff0c; 同学&#xff1a;小没苯agoe &#xff08;aaa&#xff0c;学霸&#xff01;&#xff01;&#xff01;&…

排序-快排算法对数组进行排序

目录 一、问题描述 二、解题思路 1.初始化 2.将右侧小于基准元素移到左边 3.将左侧大于基准元素移到右边 4.重复执行上面的操作 5.对分好的左、右分区再次执行分区操作 6.最终排序结果 三、代码实现 四、刷题链接 一、问题描述 二、解题思路 快排算法实现数组排序&am…

【Spring EL<二>✈️✈️ 】SL 表达式结合 AOP 注解实现鉴权

目录 &#x1f37b;前言 &#x1f378;一、鉴权&#xff08;Authorization&#xff09; &#x1f37a;二、功能实现 2.1 环境准备 2.2 代码实现 2.3 测试接口 &#x1f379;三、测试功能 3.1 传递 admin 请求 ​ 3.2 传递普通 user 请求 &#x1f37b;四、章末 &a…

【智能算法应用】基于混合粒子群-蚁群算法的多机器人多点送餐路径规划问题

目录 1.算法原理2.数学模型3.结果展示4.参考文献5.代码获取 1.算法原理 【智能算法】粒子群算法&#xff08;PSO&#xff09;原理及实现 配餐顺序&#xff1a; 采用混合粒子群算法 || 路径规划&#xff1a; 采用蚁群算法 2.数学模型 餐厅送餐多机器人多点配送路径规划&…

美创科技入选“2024网络安全提供商创新排行榜”

近日&#xff0c;DBC德本咨询公布了“2024网络安全提供商创新排行榜”&#xff0c;美创科技凭借近20年的数据安全创新耕耘&#xff0c;荣誉上榜。 此次&#xff0c;与360、华为、腾讯等互联网、网络安全头部厂商并肩上榜&#xff0c;是行业对美创的再次认可。 数据安全的发展离…

景芯SoC A72的时钟树分析

innovus的ctslog中的Clock DAG信息可以报出来CTS主要运行步骤的关键信息&#xff0c;比如clustering&#xff0c;balancing做完后的clock tree的长度&#xff0c;clock tree上所用的buffer、inverter&#xff0c;icg cell数量&#xff0c;clock skew等信息。我们以景芯SoC A72 …

搜维尔科技:Movella旗下的Xsens在人形机器人开发中得到广泛应用

人形机器人的发展正在全球范围内受到广泛关注。作为机器人领域的重要分支&#xff0c;人形机器人因其具备高度仿真的外观和动作&#xff0c;以及更贴近人类的行为模式&#xff0c;有望逐渐成为人们日常生活和工业生产中的得力助手。在中国&#xff0c;这一领域的发展尤为引人注…

解密Spring Boot:深入理解条件装配与条件注解

文章目录 一、条件装配概述1.1 条件装配的基本原理1.2 条件装配的作用 二、常用注解2.1 ConditionalOnClass2.2 ConditionalOnBean2.3 ConditionalOnProperty2.4 ConditionalOnExpression2.5 ConditionalOnMissingBean 三、条件装配的实现原理四、实际案例 一、条件装配概述 1…

C++进阶:继承

文章目录 继承的概念继承的定义方式继承关系和访问限定符基类和派生类对象的赋值转换继承中的作用域派生类中的默认成员函数构造函数拷贝构造函数赋值拷贝函数析构函数 总结 继承的概念 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允…

【全开源】Java无人共享棋牌室茶室台球室系统JAVA版本支持微信小程序+微信公众号

无人共享棋牌室系统——棋牌娱乐新体验 &#x1f3b2;引言 随着科技的不断发展&#xff0c;传统棋牌室正逐渐迈向智能化、无人化。今天&#xff0c;我要为大家介绍的就是这款引领潮流的“无人共享棋牌室系统”。它不仅为棋牌爱好者提供了全新的娱乐体验&#xff0c;更在便捷性…

【Python】数据处理:SQLite操作

使用 Python 与 SQLite 进行交互非常方便。SQLite 是一个轻量级的关系数据库&#xff0c;Python 标准库中包含一个名为 sqlite3 的模块&#xff0c;可以直接使用。 import sqlite3数据库连接和管理 连接到 SQLite 数据库。如果数据库文件不存在&#xff0c;则创建一个新数据库…

Conda安装

conda可以做到不同项目就用不同虚拟环境,这样就能做到每个项目的依赖包都是相互独立 一、windows Download Success | Anaconda 环境变量 二、nano 本次安装Archiconda的外部python版本为python3.7.1

Vue基础知识:异步DOM更新是什么?$nextTick是什么?到底应该如何使用。什么是同步?什么是异步?

要先了解异步dom更新是什么就必须先了解&#xff0c;什么是同步&#xff1f;什么是异步&#xff1f; 1.什么是同步&#xff1f;什么是异步&#xff1f; 同步&#xff08;Synchronous&#xff09;&#xff1a; 同步操作是按照代码的顺序执行的&#xff0c;每个操作都必须等待上…

【数学建模】MATLAB入门教程:插值与拟合(下)

前言 插值与拟合在数据处理和科学计算中扮演着非常重要的角色&#xff0c;它们用于估算未知数据点的值&#xff0c;帮助我们理解和预测数据趋势 一、一维插值 1、一维插值定义 已知n1个节点(,)(j0,1,...,n,其中互不相同&#xff0c;不妨设a<<...<b),求任一插值点(…

swift5 在当前控制器先dismiss后pop

如下图需要在present当前控制器时用全局变量firmwareUpgradePresentingVC先引用上一个控制器&#xff08;下面的代码亲测有效&#xff09; func dismissAndPop() {self.dismiss(animated: false) {firmwareUpgradePresentingVC.navigationController!.popViewController(animat…

Java基础面试重点-3

41. 简述线程生命周期(状态) 其它参考《多线程重点》中的说法。三种阻塞&#xff1a; 等待阻塞&#xff1a; 运行的线程执行o.wait()方法&#xff08;该线程已经持有锁&#xff09;&#xff0c;JVM会把该线程放入等待队列中。同步阻塞&#xff1a; 运行的线程在获取对象的同步…

Stable Diffusion 如何写出更优雅的 Prompt

在看了前面的课程后&#xff0c; 相信很多人都会有一个困惑&#xff0c;这个 prompt 咋写… 为什么我写的时候只能憋出来了一个 a girl, a boy, beautify … 再也想不到其他的了&#xff0c; 总感觉是吃了没文化的亏&#xff1f; 这一节课我们就来讲一讲 如何写好 prompt …

跟着AI学AI_08 NumPy 介绍

NumPy&#xff08;Numerical Python&#xff09;是一个用于科学计算的基础库&#xff0c;它为 Python 提供了支持大规模多维数组和矩阵 NumPy 介绍 NumPy&#xff08;Numerical Python&#xff09;是一个用于科学计算的基础库&#xff0c;它为 Python 提供了支持大规模多维数…

如何快速搭建自己的进销存系统?

什么是进销存系统&#xff1f; 进销存&#xff0c;是指企业管理过程中采购&#xff08;进&#xff09;—入库&#xff08;存&#xff09;—销售&#xff08;销&#xff09;的动态管理过程。进&#xff1a;指询价、采购到入库与付款的过程。进销存管理系统是对企业生产经营中物…

【Python】已完美解决:(Python键盘中断报错问题) KeyboardInterrupt

文章目录 一、问题背景二、可能出错的原因三、错误代码示例四、正确代码示例&#xff08;结合实战场景&#xff09;五、注意事项 已解决&#xff1a;Python中处理KeyboardInterrupt&#xff08;键盘中断&#xff09;报错问题 一、问题背景 在Python编程中&#xff0c;当我们运…