立体状星星（指向立体星(随便起的名）的建立与使用）

在图论中
  
  
  
  
  
  
 ，我们经常使用不同种的数据结构来储存图的信息  
  
  
  
  
  
 ，同时要适应算法的需要；

其中较为节省内存的包括了链式前向星和邻接表
 


 


 


 


 


 


 
，但是对于最基本的最短路初学者一般用不到
 
 
 
 
 
 
，因此   
   
   
   
   
   
  ，我在此介绍一种基于结构体的储存方式——“指向立体星
  
  
  
  
  
  
 ”

一 指向立体星的搭建 struct ver { int no;//节点编号 int dat;//点权 int tnum;//出度 int to[N];//通往的点（储存的数量应该等于tnum） int k1[N];//出度的边权 int edge1[N];//出度的边的编号 int fnum;//入度 int from[N];//入度边的起始点 int k2[N];//入度的边权 int edge2[N];//入度的边的编号 }t[N];

看起来变量很多
 

 

 

 

 

 

 
，实际上我列举了我能想到的所有可能用到的变量

 

 

 

 

 

 
，真正需要计算的不会是全部              ，看题就好

二 指向立体星的存储 void add(int x,int y) { t[x].tnum++; t[y].fnum++; t[x].to[t[x].tnum]=y; t[y].from[t[y].fnum]=x; }

这是最普通的添加点
 
 

 
 

 
 

 
 

 
 

 
 

 
，当然可以精简一下

void add(int x,int y) { t[x].to[++t[x].tnum]=y; t[y].from[++t[y].fnum]=x; }

如果存其他的东西












，（边的编号                    ，权值等等）函数传值时传过来就好啦~

要注意的是这个结构体里数组的下标是结构体中的一个数据 
 
 
 
 
 
 
 
 
 
 
 
 
，调用时要看清O-O!

三 实战应用

拓扑时它是最好用的



















，其他时候记得结合不同情况找最优的选择(๑•̀ㅂ•́)و✧

随机附赠一道例题(NOIP 2003 提高组第一题)

题目背景

人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统             ，在模式识别             、函数逼近及贷款风险评估等诸多领域有广泛的应用
  
  
  
  
  
  
 。对神经网络的研究一直是当今的热门方向  
 
  
 
  
 
  
 
  
 
  
 
  
，兰兰同学在自学了一本神经网络的入门书籍后












，提出了一个简化模型
  
  
  
  
  
  
 ，他希望你能帮助他用程序检验这个神经网络模型的实用性  
  
  
  
  
  
 。

题目描述

在兰兰的模型中  
  
  
  
  
  
 ，神经网络就是一张有向图
 


 


 


 


 


 


 
，图中的节点称为神经元
 
 
 
 
 
 
，而且两个神经元之间至多有一条边相连   
   
   
   
   
   
  ，下图是一个神经元的例子：

公式中的 Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值
 


 


 


 


 


 


 
。当C_i大于0时
 

 

 

 

 

 

 
，该神经元处于兴奋状态

 

 

 

 

 

 
，否则就处于平静状态
 
 
 
 
 
 
。当神经元处于兴奋状态时              ，下一秒它会向其他神经元传送信号
 
 

 
 

 
 

 
 

 
 

 
 

 
，信号的强度为Ci   
   
   
   
   
   
  。

如此．在输入层神经元被激发之后












，整个网络系统就在信息传输的推动下进行运作
 

 

 

 

 

 

 
。现在                    ，给定一个神经网络 
 
 
 
 
 
 
 
 
 
 
 
 
，及当前输入层神经元的状态（Ci）



















，要求你的程序运算出最后网络输出层的状态

 

 

 

 

 

 
。

输入格式

输入文件第一行是两个整数n（1≤n≤100）和p              。接下来n行             ，每行2个整数  
 
  
 
  
 
  
 
  
 
  
 
  
，第i+1行是神经元i最初状态和其阈值(Ui),非输入层的神经元开始时状态必然为0
 
 

 
 

 
 

 
 

 
 

 
 

 
。再下面P行












，每行由2个整数i,j及1个整数Wij
  
  
  
  
  
  
 ，表示连接神经元i,j的边权值为Wij

输出格式

输出文件包含若干行  
  
  
  
  
  
 ，每行有2个整数
 


 


 


 


 


 


 
，分别对应一个神经元的编号
 
 
 
 
 
 
，及其最后的状态2个整数间以空格分隔












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

若输出层的神经元最后状态均为0
 

 

 

 

 

 

 
，则输出 NULL 
 
 
 
 
 
 
 
 
 
 
 
 
。

输入输出样例

输入

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

输出

3 1

4 1

5 1 #include<bits/stdc++.h> using namespace std; int n,p,quan[120][120]; struct ver { int c,u,ru,chu; int ch[90]; bool ask,isin=1; }s[120]; int main() { cin>>n>>p; for(int i=1;i<=n;i++) cin>>s[i].c>>s[i].u; int a,b; for(int i=1;i<=p;i++){ cin>>a>>b>>quan[a][b]; s[b].ru++; s[a].ch[++s[a].chu]=b; s[b].isin=0; } int ans=0; while(ans<n) for(int i=1;i<=n;i++){ if((s[i].ru==0&&!s[i].isin&&s[i].c-s[i].u<=0)||(s[i].ru==0&&s[i].c==0&&s[i].isin)){ ans++; for(int j=1;j<=s[i].chu;j++) s[s[i].ch[j]].ru--; continue; } if(s[i].ru==0&&s[i].ask==0){ ans++; s[i].ask=1; if(!s[i].isin) s[i].c-=s[i].u; for(int j=1;j<=s[i].chu;j++) s[s[i].ch[j]].ru--,s[s[i].ch[j]].c+=quan[i][s[i].ch[j]]*s[i].c; } } bool ok=0; for(int i=1;i<=n;i++) if(s[i].c>0&&s[i].chu==0) { cout<<i<<" "<<s[i].c<<endl; ok=1; } else continue; if(ok==0) cout<<"NULL"<<endl; return 0; }