图论练习题

[NOIP2003]神经网络
1.题意看懂以后就是计算一下每一个入度0的点最终的状态，并且如果这个状态>0就输出出来，对于阈值，我们可以在一开始就对这些入度的0的点直接减去阈值。
2.然后就是一个拓扑排序的模型，因为我们要计算一个点的状态是需要这个点前面相连的所有点的状态而来，因此很容易想到拓扑排序。其次需要掌握链式前向星的存储方式，方便理解代码。
3.注意处理一些代码的细节，比如计算状态的时候，只有状态>0的点可以传递信号

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,p;

int din[1015],dout[1015];//入度和出度
int c[1015],u[1015];//各自的状态，阈值
vector<int>tp;//存放点的拓扑序
//---------链式前向星存图------
struct Edge{
    int to;
    int w;
    int next;
}edge[1015];
int head[1015],idx;

void add(int u,int v,int w)
{
    edge[idx].w=w;
    edge[idx].to=v;
    edge[idx].next=head[u];
    head[u]=idx++;
}
//----------------------------



void toposort()
{
   queue<int>q;
   for(int i=1;i<=n;i++) if(din[i]==0) q.push(i);
   while(q.size())
   {
       auto x=q.front();q.pop();
       tp.push_back(x);
       for(int i=head[x];i!=-1;i=edge[i].next)//链式前向星的遍历
       {
           if(--din[edge[i].to]==0) q.push(edge[i].to);
       }
       
   }
}



signed main()
{
 
   cin>>n>>p;
   for(int i=1;i<=n;i++)
   {
       cin>>c[i]>>u[i];
       if(!c[i]) c[i]-=u[i];
       //输出层可以直接减去这个阈值
   }
   
   
   //别忘记对head数组初始化
   memset(head,-1,sizeof head);
   
   
   while(p--)
   {
       int u,v,w;
       cin>>u>>v>>w;
        add(u,v,w);
       din[v]++;//别忘记入度和出度
       dout[u]++;
  
   }
   
   //对这些点进行拓扑排序
   toposort();
   
  
   //排完序后计算每点的状态
   for(int i=0;i<tp.size();i++)
   {
       int j=tp[i];
       if(c[j]>0){//只有大于0的状态才可以向其他神经元传递信号
       for(int k=head[j];k!=-1;k=edge[k].next)
       {
           c[edge[k].to]+=edge[k].w*c[j];
       }
       }
   }
   
 
   int fla=1;//检查神经元状态是否都为0
   for(int i=1;i<=n;i++)
   {
       //出度为0的点才是输出层，并且状态要大于0
       if(c[i]>0 and !dout[i]) cout<<i<<" "<<c[i]<<endl,fla=0;
   }
   if(fla) cout<<"NULL";
  
    
    
}