【题解】P1038 神经网络
Binaries
·
·
个人记录
前言
这是本蒟蒻第一次写题解，万望大佬们指导~
（注：思路如有雷同，纯属巧合！）
思路
我们来从样例入手~
分析算法
首先，由题意可知，当一个神经元处于兴奋状态且无法继续传递信号时，这个神经元一定位于输出层。若一个神经元不受任何神经元影响，这个神经元一定为于输入层
在上图中，1号、2号神经元位于输入层，3号、4号、5号神经元位于输出层，仔细观察就能发现，位于输入层的神经元的入度为0，位于输出层的神经元的出度为0！
剖析答案时，一层算完后我们需要删除该层以找到下一层，下一层仍是由入度为0的神经元构成的~
根据题目中所给公式
**也就是说，如果分为若干层的话，下一层的答案必须在上一层的答案全部算出后才能计算**
此外，由“每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。”易知，上层答案会影响下层答案，而下层答案不会影响上层答案，引用一个DP的特性说就是**无后效性**~
还有一点，入度先为0的点是先参与计算的，也就是**先进先出**，也就是我们需要用到队列~
其实到这里算法已经很明确了，就是： **拓扑排序**
## 亿些坑点
1.由于输入层不受任何其他神经元影响，无需接受信号，因此**也无需减去阈值**。
2.神经元状态≤0时**不继续向下传递信号**，因此并不是所有神经元都可以更新下一层的答案。
3.计算答案时要在求完和后再减去阈值。（这个还好）
4.或许有dalao在考虑输入层≤0的情况，其实，根据坑点2.可知输入层中状态≤0的神经元没有任何用处。也就是说，写代码时，我们**只需要考虑初始状态＞0的神经元**。
# 代码
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN(110),MAXP(12100);
queue<int> tp;
struct edge{
int to,nxt,dis;
}ed[MAXP];
int head[MAXN],in[MAXN],n,p,u[MAXN],c[MAXN],cnt;
bool ians=true;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline void add(int from,int to,int dis){
ed[++cnt].to=to;
ed[cnt].nxt=head[from];
ed[cnt].dis=dis;
head[from]=cnt;
in[to]++;
}
int main(){
n=read();p=read();
for(register int i=1;i<=n;i++){
c[i]=read();
u[i]=read();
if(c[i]) tp.push(i);
}
for(register int i=1;i<=p;i++){
int u=read();
int v=read();
int d=read();
add(u,v,d);
}
while(!tp.empty()){
int now=tp.front();
tp.pop();
if(c[now]<=0) continue;
for(register int i=head[now];i;i=ed[i].nxt){
int to=ed[i].to;
c[to]+=(ed[i].dis*c[now]);
if(!--in[to]){
tp.push(to);
c[to]-=u[to];
}
}
}
for(register int i=1;i<=n;i++){
if(!head[i]&&c[i]>0){
printf("%d %d\n",i,c[i]);
ians=false;
}
}
if(ians){
printf("NULL\n");
}
return 0;
}
```
# 后语
本人的LaTeX水平实在是……打公式真的打了好久……
**感谢神仙们阅读！**