[Luogu] 洛谷 P1038 题解【神经网络】

//当神经元处于兴奋状态时,下一秒它会向其他神经元传送信号

也就是说如果小于0，就不会向下传值（像#3）

多出几个像#3这样的点应该会卡死很多人吧

反正我是入坑了（逃）

废话不多说，开讲：

像这种子工程之间先后关系非常明显的题一般都是拓扑排序

拓扑排序便于我们处理每一层向下的结果

#include<bits/stdc++.h>
using namespace std;
int st[10001],head[10001],n,p,last[10001];
int top,in_du[10001],out_du[10001],num_edge,c[10001],u[10001];
struct Edge
{
    int next,to,d;
}edge[10010];//热爱前向星的我
inline void add_edge(int from,int to,int dis)
{
    edge[++num_edge].next=head[from];
    edge[num_edge].to=to;
    edge[num_edge].d=dis;
    head[from]=num_edge;
}
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>u[i];
        if(c[i]>0) st[++top]=i;
    }
    for(int i=1;i<=p;i++)
    {
        int x,y,d;
        cin>>x>>y>>d;
        add_edge(x,y,d);
        in_du[y]++;
        out_du[x]++;//判断是否为输出层
    }
    int l=0;
    while(top>0)
    {
        int x=st[top--];
        for(int i=head[x];i;i=edge[i].next)
        {
            in_du[edge[i].to]--;
            if(c[x]>0) c[edge[i].to]+=edge[i].d*c[x];//避免#3这样的坑点
            if(in_du[edge[i].to]==0)
            {
                st[++top]=edge[i].to;
                c[edge[i].to]-=u[edge[i].to];
            }
        }
    }
    bool bj=false;//判断输出NULL
    for(int i=1;i<=n;i++)
      if(out_du[i]==0&&c[i]>0) cout<<i<<‘ ‘<<c[i]<<endl,bj=true;
    if(bj==false) cout<<"NULL";
}