题解 | #神经网络#

建议先去学习一下拓扑排序再来

思路和题目意思就不做过多赘述了

要点都在注释里了

神经网络

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = N * N;
//牛客的话没有给边的数量的范围，给定的n的范围好像也不太靠谱，你n给太小的话就会超时
//具体开多少搞不不清楚，反正开1010就能过

int n, m;
int c[N], u[N];//每个神经元的状态和阈值
int din[N], dout[N];//每个点的入度和出度 
//入度是因为拓扑排序需要 出度是用来判断哪些神经元是输出层(出度为0的即为输出层)
int h[N], w[M], e[M], ne[M], idx;//邻接表
int q[N];//用队列实现拓扑排序，并且把排序后的神经元存储下来

void add(int a, int b, int c)
{
	w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void topsort()
{
	int hh = 0, tt = -1;//一开始队列里没有任何东西所以tt = -1
	for(int i = 1; i <= n; i ++)//扫描所有点
		if(!din[i])//入度为0的进入队列
			q[++ tt] = i;
	
	while(hh <= tt)
	{
		int t = q[hh ++];
		for(int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if(-- din[j] == 0)//把当前点连向其他点的边全部去掉，再把入度为0的点入队
				q[++ tt] = j;
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
	{
		cin >> c[i] >> u[i];
		if(!c[i]) c[i] -= u[i];
        //这里直接按照公式里c[i]的计算方法减去u[i],后面只用加个c[j] * Wji就行了
        //注意：输入层的神经元是不用减去阈值的，所以我这里只处理c[i] = 0的点的阈值(因为题目说了：非输入层的神经元开始时状态必然为0)
        //但是题目好像没有明说这点
	}
	
	memset(h, -1, sizeof h);//建图之前的初始化
	while(m --)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);//单向边
		dout[a] ++, din[b] ++;//更新出度入度
	}
	topsort();
	
    //按照之前排好序的神经元的顺序更新所有神经元的状态
    //神经元的顺序都被存储到队列里了 队列是从下标0开始的 所以这里和别地不一样 i从0开始
	for(int i = 0; i < n; i ++)
	{
		int j = q[i];
		if(c[j] > 0)//题目说了 状态>0的神经元才会向其他神经元传送信号
		{
			for(int k = h[j]; ~k; k = ne[k])
				c[e[k]] += c[j] * w[k];
		}
	}

    bool flag = true;//标记一下看看是不是所有神经元最后状态全部为0
    for (int i = 1; i <= n; i ++ )
        //dout[i] = 0的点才是输出层 并且状态>0的神经元才会传递信号 这里需要同时满足两个条件
        if (!dout[i] && c[i] > 0)
        {
            printf("%d %d\n", i, c[i]);
            flag = false;
        }

    if (flag) puts("NULL");

    return 0;	
}