游客 Signup | Login
中文 | En

2356 - 神经网络

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 125 MB

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

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经

元之间至多有一条边相连，下图是一个神经元的例子： 

<span style="line-height:1.5;"><img src="http://tk.hustoj.com:80/attached/image/20140113/20140113165437_34413.jpg" alt="" /></span> 


<span style="line-height:1.5;">图中，X1—X3是信息输入渠道，Y1—Y2是信息输出渠道，C1表示神经元目前的状态，Ui是阈值，可视为神经元的一个内在参数。</span> 


<span style="line-height:1.5;">神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。</span> 


<span style="line-height:1.5;"><img src="http://tk.hustoj.com:80/attached/image/20140113/20140113165626_59496.jpg" alt="" /><br />


<span style="line-height:1.5;">兰兰规定，</span><span style="line-height:1.5;">C<sub>i</sub></span><span style="line-height:1.5;">服从公式：（其中</span><span style="line-height:1.5;">n</span><span style="line-height:1.5;">是网络中所有神经元的数目）</span> 


<span style="line-height:1.5;"><img src="http://tk.hustoj.com:80/attached/image/20140113/20140113165648_37755.jpg" alt="" /><br />


<span style="line-height:1.5;">公式中的Wji（可能为负值）表示连接j号神经元和 i号神经元的边的权值。当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。<br />

如此，在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。
现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网络输出层的状态。 

<span style="line-height:1.5;"><br />

Input

每组输入第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。


Output

每组输出包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！
若输出层的神经元最后状态均为 0，则输出 NULL。

<br />

Examples

Input Format

5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1

Output Format

3 1
4 1
5 1

Solution C++

//神经网络
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cctype>

using namespace std;

const int N = 205;
struct Edge{
	int to,next,wei;
}edge[N * N];

struct Node{
	int c,u;
	Node (){
		c = 0; u = 0;
	}
}g[N];

int head[N],edgen = 0,rudu[N],n,p;
bool chudu[N];

inline int Read(){
	bool neg = false;
	char tmp = getchar();
	int rtn = 0;
	while (!isdigit(tmp)){
		if (tmp == '-') neg = true;
		tmp = getchar();
	}
	while (isdigit(tmp)){
		rtn = rtn * 10 + tmp - '0';
		tmp = getchar();
	}
	if (neg) rtn -= 2*rtn;
	return rtn;
}

inline void Add_Edge(int x,int y,int w){
	edge[edgen].to = y;
	edge[edgen].next = head[x];
	edge[edgen].wei = w;
	head[x] = edgen++;
}

void Rudu(){
	for (int i = 1;i <= n; i++)
		for (int p = head[i];p != -1;p = edge[p].next)	
			rudu[edge[p].to]++,chudu[i] = true;
}

int search(int k){
	if (!chudu[k]) return g[k].c;
	int rtn = 0;
	for (int p = head[k];p != -1;p = edge[p].next){
		int use = search(edge[p].to);
		if (use > 0)
			rtn += use * edge[p].wei;
	}
	rtn -= g[k].u;
	return rtn;
}

int main(){
	n = Read(),p = Read();
	for (int i = 1;i <= n; i++){
		g[i].c = Read();
		g[i].u = Read();
	}
	memset(head,-1,sizeof(head));
	for (int i = 1,x,y,w;i <= p; i++){
		x = Read();
		y = Read();
		w = Read();
		Add_Edge(y,x,w);
	}
	memset(rudu,0,sizeof(rudu));
	memset(chudu,false,sizeof(chudu));
	Rudu();
	bool flag = false;
	for (int i = 1;i <= n; i++)
		if (!rudu[i]){
			int use = search(i);
			if (use > 0){
				cout << i << " " << use << endl;
				flag = true;
			}
		}
	if (!flag) cout << "NULL\n";
	return 0;
}
/*
6 8
1 0
1 0
0 1
0 1
0 1
0 1
1 3 5
1 4 3
2 3 1
2 4 2
4 6 2
4 5 1
3 5 2
3 6 1
*/
/*
7 7
2 0
4 0
0 1
0 1
0 1
0 1
0 1
1 3 -2
1 4 1
3 6 -1
4 6 3
4 7 5
2 5 1
5 7 -1
*/
请先登陆