【题解】神经网络

题目
分析
Code
后记

题目

题目来源：NOIP2003 提高组第一题。

评测地址：LG1038。

题目背景

人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。

题目描述

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：

图中，(X_1)−(X_3) 是信息输入渠道，(Y_1)−(Y_2) 是信息输出渠道，(C_i) 表示神经元目前的状态，(U_i) 是阈值，可视为神经元的一个内在参数。神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经元分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子：

兰兰规定，(C_i) 服从公式：（其中 (n) 是网络中所有神经元的数目）

[large{C_i=sumlimits_{(j,i) in E} W_{j,i}C_{j}-U_{i}} ]

公式中的 (W_{j,i})（可能为负值）表示连接 (j) 号神经元和 (i) 号神经元的边的权值。当 (C_i) 大于 (0) 时，该神经元处于兴奋状态，否则就处于平静状态。

当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为 (C_i)。如此，在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。

现在，给定一个神经网络，及当前输入层神经元的状态（(C_i)），要求你的程序运算出最后网络输出层的状态。

输入格式

输入文件第一行是两个整数 (n) 和 (p)。

接下来 (n) 行，每行 (2) 个整数，第 (i+1) 行是神经元 (i) 最初状态 (C_i) 和其阈值 (U_i)，非输入层的神经元开始时状态必然为 (0)。

再下面 (p) 行，每行由 (2) 个整数 (i)、(j) 及 (1) 个整数 (W_{i,j})，表示连接神经元 (i) 和 (j) 的边权值为 (W_{i,j})。

输出格式

输出文件包含若干行，每行有 (2) 个整数，分别对应一个神经元的编号，及其最后的状态，(2) 个整数间以空格分隔。

仅输出最后状态大于 (0) 的输出层神经元状态，并且按照编号由小到大顺序输出。若输出层的神经元最后状态均为 (0)，则输出 NULL。

数据范围与约定

(1le nle 100)

分析

这道题的指向性非常明确，就是让我们每一个点每一个点地去算值，只不过要用到前驱节点，而且我们要自行确定输入节点。

显然，这是一道拓扑排序的模板题。神经网络结构满足 DAG，且我们就要进行类似 DP 一样的操作。我们可以使用拓扑排序确定顺序，再进行统计。

相比之下，还有一种方法显得更为简洁，那就是使用宽搜。「层状」的结构让我们想起这种方法。我们只需要在宽搜拓展以后进行统计即可。

（实质上宽搜和拓扑排序实现方法类似，只不过拓扑排序的目的与宽搜不同，前者是得到顺序，后者则是遍历或者搜索答案）

Code

这两种方法都是可以的，笔者这里采用了宽搜实现。

#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
const int max_n = 100;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll g[max_n][max_n], sta[max_n], upp[max_n];
int ind[max_n] = {}, oud[max_n] = {};

queue<int> ids;

int main()
{
	memset(g, 0x3f, sizeof(g));

	int n, m, ta, tb;
	ll tmp;
	bool flag;

	scanf("%d%d", &n, &m);

	for (int i = 0; i < n; i++)
		scanf("%lld%lld", sta + i, upp + i);
	
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &ta, &tb);
		scanf("%lld", &g[ta-1][tb-1]);

		oud[ta-1]++, ind[tb-1]++;
	}

	for (int i = 0; i < n; i++)
		if (!ind[i])
			ids.push(i);
	
	while (!ids.empty())
	{
		ta = ids.front();
		ids.pop();

		for (int i = 0; i < n; i++)
			if (g[ta][i] != INF)
			{
				tmp = -upp[i];
				
				for (int j = 0; j < n; j++)
					if (g[j][i] != INF)
						tmp += sta[j] * g[j][i];
				
				if (tmp > 0)
					sta[i] = tmp;
				
				ids.push(i);
			}
	}

	flag = false;
	for (int i = 0; i < n; i++)
		if (!oud[i] && sta[i] > 0)
		{
			flag = true;
			printf("%d %lld
", i + 1, sta[i]);
		}
	
	if (!flag)
		puts("NULL");

	return 0;
}

后记

这道题有一个小问题——没有提到 (U_i) 等整数的数据范围。这导致我紧张兮兮地用了 long long，但后来看看没有什么必要。