题解 P1038 【神经网络】
teafrogsf
2017-10-19 20:48:37
[日常宣传博客。](http://teafrog26.lofter.com/)
题目已经~~显然地~~告诉我们，我们需要从入度为0的点开始遍历，直到出度为0的点，从这里我们就可以~~显然地~~看出来这是一个拓扑排序。
但题目的细节给出**在输入层神经元被激发之后**，说明如果是输入层，那么u[i]为1或0都没有关系。
## 它一定会被激活。
于是我们需要预处理这种情况，并预处理出度为0的点来方便输出。
（给予新人）拓扑排序可以把一个DAG（有向五环图）里所有的点排成一个线性序列，这个序列保证一条边的from点在to点之前输出。
我的代码长度只有50行，编程复杂度应该是比较低的，非常友好XD
```cpp
#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;
}
```