题解 P1038 【神经网络】

· · 题解

这道题我才不会承认我用的思想其实是搜索233

其实不需要使用正规的有向图存储方法，也就是那个t[i][j]=1

可以使用结构体存储一个神经元的所有输入和输出，输出边统计是0的神经元自然是输出层，输入边统计是0的也就是输入层

随后扫描一遍数组，遇到输出层神经元就上一发递归搜索，即递归搜索它的前驱，碰到状态不为零或已经回到输入层就返回当前神经元的状态

最后累加

有一个坑点一开始坑了我六十分，那就是当c[i]<0时按c[i]=0来算

最后上代码

#inlude<iostream>
#inlude<cstdio>
struct data{
    int h[105][2];
    int t[105][2];
    int tot,sum;
    int u,k;
    data(){tot=sum=0;}
}f[105];
int search(int i)
{
    if(f[i].k||f[i].tot==0)    return f[i].k;
    int ans=0;
    for(int j=1;j<=f[i].tot;++j)
        ans+=(    search(f[i].h[j][0]) * f[i].h[j][1]    );
    ans-=f[i].u;
    if(ans<0)    ans=0;
    return ans;
}
int main()
{
    int n,p;
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&f[i].k,&f[i].u);
    int a,b,c;
    for(int i=1;i<=p;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        f[b].h[++f[b].tot][0]=a;
        //cout<<b<<" "<<f[b].tot<<endl;
        f[b].h[f[b].tot][1]=c;
        f[a].t[++f[a].sum][0]=b;
        f[a].t[f[a].sum][1]=c;
    }
    bool flag=0;
    for(int i=1;i<=n;++i)
    {
        if(f[i].sum==0)
        {
            f[i].k=search(i);
            if(f[i].k)
            {
                cout<<i<<" "<<f[i].k<<endl;
                flag=1;
            }
        }
    }
    if(!flag)
        cout<<"NULL"<<endl;
    //cout<<endl<<endl<<endl;
    /*for(int i=1;i<=n;++i)
        cout<<f[i].sum<<" "<<f[i].tot<<" "<<f[i].k<<endl;*/
    return 0;
}

细心的同学会发现防抄袭的修改 就这样