P1038 神经网络网页链接P1038 神经网络题目背景人工神经网络Artificial Neural Network是一种新兴的具有自我学习能力的计算系统在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向兰兰同学在自学了一本神经网络的入门书籍后提出了一个简化模型他希望你能帮助他用程序检验这个神经网络模型的实用性。题目描述在兰兰的模型中神经网络就是一张有向图图中的节点称为神经元而且两个神经元之间至多有一条边相连下图是一个神经元的例子神经元编号为i ii图中X 1 ∼ X 3 X_1 \sim X_3X1​∼X3​是信息输入渠道Y 1 ∼ Y 2 Y_1 \sim Y_2Y1​∼Y2​是信息输出渠道C i C_iCi​表示神经元目前的状态U i U_iUi​是阈值可视为神经元的一个内在参数。神经元按一定的顺序排列构成整个神经网络。在兰兰的模型之中神经网络中的神经元分为几层称为输入层、输出层和若干个中间层。每层神经元只向下一层的神经元输出信息只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。兰兰规定C i C_iCi​服从公式其中n nn是网络中所有神经元的数目C i ( ∑ ( j , i ) ∈ E W j i C j ) − U i C_i\left(\sum\limits_{(j,i) \in E} W_{ji}C_{j}\right)-U_{i}Ci​​(j,i)∈E∑​Wji​Cj​​−Ui​公式中的W j i W_{ji}Wji​可能为负值表示连接j jj号神经元和i ii号神经元的边的权值。当C i C_iCi​大于0 00时该神经元处于兴奋状态否则就处于平静状态。当神经元处于兴奋状态时下一秒它会向其他神经元传送信号信号的强度为C i C_iCi​。如此在输入层神经元被激发之后整个网络系统就在信息传输的推动下进行运作。现在给定一个神经网络及当前输入层神经元的状态C i C_iCi​要求你的程序运算出最后网络输出层的状态。输入格式输入文件第一行是两个整数n nn1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100和p pp。接下来n nn行每行2 22个整数第i 1 i1i1行是神经元i ii最初状态和其阈值U i U_iUi​非输入层的神经元开始时状态必然为0 00。再下面p pp行每行有两个整数i , j i,ji,j及一个整数W i j W_{ij}Wij​∣ W i j ∣ ≤ 10 9 |W_{ij}|\leq 10^9∣Wij​∣≤109表示连接神经元i , j i,ji,j的边权值为W i j W_{ij}Wij​。输出格式输出文件包含若干行每行有2 22个整数分别对应一个神经元的编号及其最后的状态2 22个整数间以空格分隔。仅输出最后状态大于0 00的输出层神经元状态并且按照编号由小到大顺序输出。若输出层的神经元最后状态均小于等于0 00则输出NULL。输入输出样例 #1输入 #15 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输出 #13 1 4 1 5 1说明/提示【题目来源】NOIP 2003 提高组第一题解题思路本题是有向无环图上的逐层传播与状态计算的经典问题。神经网络可以看作一张有向无环图每个神经元是一个节点边表示信号传递并带有权值。每个神经元的状态由公式C i ∑ ( j , i ) ∈ E W j i C j − U i C_i \sum_{(j,i) \in E} W_{ji} C_j - U_iCi​∑(j,i)∈E​Wji​Cj​−Ui​决定当C i 0 C_i 0Ci​0时处于兴奋状态并向下一层传递信号。需要计算最终输出层出度为0 00中状态大于0 00的神经元。1. 问题等价转化神经网络分层信号从输入层逐层向输出层传播。输入层神经元的初始状态已知非输入层初始状态为0 00。每个神经元的阈值U i U_iUi​可以在计算时减去。为了简化对于非输入层初始化时令C i − U i C_i -U_iCi​−Ui​对于输入层初始状态已给定不减去阈值因为输入层的状态是直接给出的不经过公式计算。传播过程只有兴奋的神经元C i 0 C_i 0Ci​0才会向下游发送信号信号的强度为C i C_iCi​。对于每条边( i , j ) (i, j)(i,j)目标神经元j jj的状态会增加W i j × C i W_{ij} \times C_iWij​×Ci​。由于图是有向无环的且输入层所有节点同时开始传播可以按层顺序依次计算。使用队列进行广度优先遍历保证每个节点在处理时已经接收完所有前驱的信号。2. 算法实现建图使用链式前向星存储有向边记录每条边的终点to、权值val和下一个边的指针nxt。初始化读入n , p n, pn,p。对于每个节点i ii读入初始状态c i c_ici​和阈值U i U_iUi​。如果c i 0 c_i 0ci​0输入层将其加入队列q并标记vis[i] 1。否则令c i c i − U i c_i c_i - U_ici​ci​−Ui​即c i − U i c_i -U_ici​−Ui​表示初始状态为负的阈值。同时用out[i]记录节点是否有出边初始为0 00每读入一条边(u, v, w)建边并令out[u] 1。传播BFS当队列非空时取出队首节点h。如果c[h] 0跳过不兴奋不传播。否则遍历h的所有出边令目标节点t e[i].to更新c[t] e[i].val * c[h]。如果t尚未访问!vis[t]将t入队并标记vis[t] 1。由于初始队列包含所有输入层节点且队列按 FIFO 顺序处理实际上实现了按层传播保证每个节点在处理时已累加完所有前驱的信号。输出遍历所有节点i 1 ∼ n i 1 \sim ni1∼n。如果节点i ii没有出边out[i] 0且c[i] 0输出i和c[i]。如果没有任何节点满足条件输出NULL。3. 复杂度分析时间复杂度每个节点最多入队一次每条边最多被处理一次因此总时间复杂度为O ( n p ) O(n p)O(np)。n ≤ 100 n \le 100n≤100p ≤ n 2 p \le n^2p≤n2运算量极小。空间复杂度需要存储邻接表链式前向星、状态数组、访问标记等空间复杂度O ( n p ) O(n p)O(np)非常小。总结本题通过队列进行逐层传播巧妙地利用初始队列包含所有输入层节点保证了传播顺序的正确性。将阈值处理为初始负值简化了状态计算公式。使用vis数组防止节点重复入队确保每个节点只处理一次。最终按编号顺序输出满足条件的输出层神经元状态。算法简单高效是图论中拓扑传播的典型应用。代码简要说明结构体E存储边的终点to、权值val和下一个边的索引nxt。结构体A用于存储答案节点代码中定义了但未使用排序实际直接按顺序输出。全局数组c[MAXN]存储神经元状态hd[MAXN]为链式前向星头指针out[MAXN]标记出度vis[MAXN]标记是否已入队。函数bd(u, v, w)添加一条从u到v权值为w的有向边。主函数读入n , m n, mn,m。初始化每个节点的状态和阈值输入层节点入队非输入层节点状态减去阈值。读入边建图标记出度。队列 BFS 传播信号。遍历节点输出出度为0 00且状态 0 00的节点若没有则输出NULL。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll MAXN101;structE{ll to,val,nxt;}e[MAXN*MAXN];structA{ll id,val;}ans[MAXN];ll n,m,u,v,w,U,c[MAXN],hd[MAXN],out[MAXN],vis[MAXN];queuellq;ll tot0,fg0;boolcm(A a,A b){returna.idb.id;}voidbd(ll u,ll v,ll w){tot;e[tot].tov;e[tot].valw;e[tot].nxthd[u];hd[u]tot;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,m);for(ll i1;in;i){vis[i]out[i]0;scanf(%lld%lld,c[i],U);if(c[i]0){q.push(i);vis[i]1;}elsec[i]-U;}for(ll i1;im;i){scanf(%lld%lld%lld,u,v,w);bd(u,v,w);out[u]1;}while(!q.empty()){ll hq.front();q.pop();if(c[h]0)continue;for(ll ihd[h];i;ie[i].nxt){ll te[i].to;c[t]e[i].val*c[h];if(!vis[t]){q.push(t);vis[t]1;}}}for(ll i1;in;i){if(!out[i]c[i]0){printf(%lld %lld\n,i,c[i]);fg1;}}if(!fg)puts(NULL);return0;}