2019-05-21 P1038 神经网络

题目链接：https://www.luogu.org/problemnew/show/P1038

使用拓扑排序的思想处理的神经网络：
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=101;
typedef vector<int> vec;
struct Node{
    int v,w;
    Node(int v=0,int w=0):v(v),w(w){}
}; 
vector<Node>G[maxn];
int n,p,U[maxn],C[maxn],in[maxn],out[maxn];

vec solve(){
    vec ans;
    queue<int>que;
    for(int i=1;i<=n;i++){
        if(in[i]==0) {
            U[i]=0;//第一层神经元不需要减去阈值，所以处理为0 
            que.push(i);
        }
    }
    while(!que.empty()){
        int u=que.front(); que.pop();
        C[u]-=U[u];//减去阈值
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].v;
            int w=G[u][i].w;
            in[v]--;
            if(in[v]==0) que.push(v);//如果入度为0，那么可以加入队列中 
            if(C[u]>0) C[v]+=w*C[u];//如果处于兴奋状态，对下一层的神经元传递信号 
        } 
    }
    for(int i=1;i<=n;i++){
        if(out[i]==0 && C[i]>0){
            ans.push_back(i);
        }
    }
    return ans; 
}
int main(void){
    cin>>n>>p;
    for(int i=1;i<=n;i++) cin>>C[i]>>U[i];
    for(int i=1;i<=p;i++){
        int u,v,w;
        cin>>u>>v>>w;
        in[v]++;
        out[u]++;
        G[u].push_back(Node(v,w));      
    }
    vec ans=solve();
    if(ans.size()==0) cout<<"NULL";
    else{
        for(int i=0;i<ans.size();i++){
            int u=ans[i];
            cout<<u<<" "<<C[u]<<endl; 
        }
    }
    return 0;
}

没有什么固定的思路，就是使用了点bfs和拓扑排序的思路：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int maxn=101;
struct Node{
    int v,w;
    Node(int v=0,int w=0):v(v),w(w){} 
};
vector<Node> Adj[maxn];
int n,p,U[maxn],C[maxn],level[maxn],in[maxn],out[maxn],used[maxn];

vector<int> solve(){
    queue<int>que;
    for(int i=1;i<=n;i++){
        if(in[i]==0 && C[i]>0){//如果是输入层并且处于兴奋状态 
            que.push(i);//加入队列 
            used[i]=true;//记录是否加入队列 
        }
    }
    while(!que.empty()){//使用bfs的思想进行一层一层的处理 
        int u=que.front(); que.pop();
        //当一个非输入层的神经元出队列的时候，减去阈值
        if(in[u]!=0) C[u]-=U[u];//此时已经计算出了状态 
        if(C[u]<=0) continue;//如果这个神经元处于平静状态，不需要往下处理了 
        for(int i=0;i<Adj[u].size();i++){//这个神经元向下层传递信号 
            int v=Adj[u][i].v;
            int w=Adj[u][i].w;
            //如果当前的神经元兴奋 
            //对下一层输出信号 
            C[v]+=w*C[u]; 
            if(!used[v]){
                used[v]=true;
                que.push(v);
            }
        }
    }

    vector<int>vec;
    for(int i=1;i<=n;i++)
        if(out[i]==0 && C[i]>0)//如果是输出层
            vec.push_back(i);
    return vec;
}
int main(void){
    cin>>n>>p;
    for(int i=1;i<=n;i++) cin>>C[i]>>U[i];
    int u,v,w;
    for(int i=1;i<=p;i++){
        cin>>u>>v>>w;
        Adj[u].push_back(Node(v,w));
        in[v]++;//记录有输入边的顶点，没有输入边的顶点是输出层 
        out[u]++;
    }
    vector<int> vec = solve();
    
    bool isnull; 
    if(vec.size()==0) isnull=true;
    else isnull=false;
    
    if(isnull) cout<<"NULL"<<endl;
    else{
        for(int i=0;i<vec.size();i++){
            int u=vec[i];
            cout<<u<<" "<<C[u]<<endl;
        } 
    } 
    return 0;
}