星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P1038 【神经网络】

posted on 2017-10-19 20:48:37 | under 题解 |

日常宣传博客。

题目已经显然地告诉我们,我们需要从入度为0的点开始遍历,直到出度为0的点,从这里我们就可以显然地看出来这是一个拓扑排序。

但题目的细节给出在输入层神经元被激发之后,说明如果是输入层,那么u[i]为1或0都没有关系。

它一定会被激活。

于是我们需要预处理这种情况,并预处理出度为0的点来方便输出。

(给予新人)拓扑排序可以把一个DAG(有向五环图)里所有的点排成一个线性序列,这个序列保证一条边的from点在to点之前输出。

我的代码长度只有50行,编程复杂度应该是比较低的,非常友好XD

#include<cstdio>
#include<queue>
#define neko 110
#define meko 10010
#define f(i,a,b) for(register int i=a;i<=b;++i)
struct node
{
    int u,v,w,next;
}e[meko];
int c[neko],u[neko],head[neko],dgr[neko],dgp[neko],n,m,t;
void add(int x,int y,int z)
{
    e[++t].u=x;
    e[t].v=y;
    e[t].w=z;
    e[t].next=head[x];
    head[x]=t;
    ++dgr[y],++dgp[x];
}
void topsort()
{
    std::queue<int>q;int x,v;
    f(i,1,n)if(!dgr[i])q.push(i);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(register int i=head[x];i;i=e[i].next)
        {
            v=e[i].v;
            --dgr[v];
            if(c[x]>0)c[v]+=c[x]*e[i].w;
            if(!dgr[v])q.push(v);
        }
    }
}
int main()
{
    int x,y,z;bool flag=0;
    scanf("%d%d",&n,&m);
    f(i,1,n)
    {
        scanf("%d%d",&c[i],&u[i]);
        if(c[i]==0)c[i]-=u[i];
    }
    f(i,1,m)scanf("%d%d%d",&x,&y,&z),add(x,y,z);
    topsort();
    f(i,1,n)if(c[i]>0&&dgp[i]==0)printf("%d %d\n",i,c[i]),flag=1;//dgp is about output
    if(!flag)printf("NULL\n");return 0;
}