NOIP2003年提高组复赛上机试题神经网络

本文主要是介绍NOIP2003年提高组复赛上机试题神经网络，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

NOIP2003年提高组复赛上机试题神经网络

1.问题分析
2.具体代码
3.总结

题目链接

是否看了题解找思路

1.问题分析

1.碰到一道题干很复杂的题目，要先弄清楚题目到底在干什么，把样例在纸上模拟出来。
2.思考一般情况，分析题目的考察的知识点（例如本题考查的就是拓扑排序，恰巧我不熟练，看了题解才明白了思路）。
3.设计数据结构，需要记录下哪些数据，如何存储、更新数据，如何存储图。

在本题中，核心思路就是将结点先进行拓扑排序，在遍历一遍。
对于一个结点，应该存储其出度，入读（第一次写出入度），子节点的链表。
在拓扑排序中，最好用数组实现队列，y总说过：用数组实现队列可以获取队列中间的元素。不过top_sort()函数很值得学习。
邻接表仅仅用于存储图，只在遍历一点的子节点时使用。（应该明确邻接表能实现的功能，将邻接表模块化思考，不要乱用邻接表！！）

2.具体代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//本来打算直接用queue，后来发现不行
using namespace std;
const int N =105;
int h[N],e[N*N],W[N*N],ne[N*N],idx,n,p;
int chu[N],yu[N];//chu的意思是初始值，yu的意思是阈值。。。
int din[N],dout[N],q[N];//q是队列
void add(int a,int b,int w)
{e[idx]=b;W[idx]=w;ne[idx]=h[a];h[a]=idx++;
}
void top_sort()
{int hh=0,tt=-1;for(int i=1;i<=n;i++){if(din[i]==0){q[++tt]=i;chu[i]+=yu[i];//输入点先加一次阈值，与之后的减去一次阈值抵消}}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){if(--din[e[i]]==0)//我觉得这个地方的处理很巧妙{q[++tt]=e[i];}}}}
int main()
{cin>>n>>p;memset(h,-1,sizeof h);for(int i=1;i<=n;i++)   cin>>chu[i]>>yu[i];for(int i=1;i<=p;i++){int a,b,w;cin>>a>>b>>w;add(a,b,w);din[b]++;dout[a]++;}top_sort();for(int i=0;q[i]!=0;i++)//按拓扑序遍历所有点{int now=q[i];chu[now]-=yu[now];if(chu[now]>0)for(int j=h[now];j!=-1;j=ne[j]){int k=e[j];chu[k]+=(chu[now]*W[j]);//记得乘以权重！！}}bool had_print=false;for(int i=1;i<=n;i++){if(dout[i]==0&&chu[i]>0){printf("%d %d\n",i,chu[i]);had_print=true;}}if(!had_print){printf("NULL\n");}return 0;
}