拓扑排序

算法一，就是模板，按照模板来写代码，不容易出错，且写代码速度快，以邻接表为数据结构
算法二，是我写的代码，速度慢不说，时间复杂度o(n^2)，以邻接矩阵为数据结构
这个模板还是要背下来，我已经遇到2次了

算法1

(拓扑排序) O(n+m)

𝑂(𝑛+𝑚)
这道题目需要注意输入层的初始状态不用减去阈值。

为了保证使用每个点的状态去更新其他点时，该点的状态已被计算完毕，我们需要使用拓扑序来计算每个点的值。

计算完拓扑序列后，我们只需从前往后递推一遍，即可求出每个点的最终状态值。

时间复杂度
拓扑排序和递推的时间复杂度均是 O(n+m) 𝑂(𝑛+𝑚),
因此总时间复杂度是 O(n+m) 𝑂(𝑛+𝑚)
。

#include <bits/stdc++.h>
using namespace std;

const int N=110,M=N*N/2;          //如果M不够例子的，则手动修改增加

int n,m;
int head[N],e[M],w[M],next1[M],idx;//邻接表
int c[N],u[N],din[N],dout[N];
int q[N];//队列

void add(int a,int b,int c){            //头插法
    w[idx]=c,e[idx]=b,next1[idx]=head[a],head[a]=idx++;
}

void topsort(){
    int tail=0,top=-1;
    for(int i=1;i<=n;i++){
        if(!din[i]){
            q[++top]=i;
        }
    }

    while(tail<=top){
        int t =q[tail++];
        for(int i=head[t];~i;i=next1[i]){
            int j=e[i];
            if(--din[j] == 0){
                q[++top]=j;
            }
        }
    }
}

int main(){
    int i;
    idx=1;
    memset(head,-1,sizeof head);
    cin >> n >> m;
    for(i=1;i<=n;i++){
        cin >> c[i];
        cin >> u[i];
        if(!c[i])   c[i]-=u[i];  //未激活情况下，一开始的状态减去该阈值。
    }
    for(i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        din[b]++,dout[a]++;
    }

    topsort();                  //此时，q数组的元素顺序就是top排序

    for(i=0;i<n;i++){
        int j= q[i];
        if(c[j] > 0){
            for(int t = head[j];~t;t=next1[t]){
                c[e[t]]+=w[t]*c[j];
            }
        }
    }
    bool flag = true;
    for(i =1;i<=n;i++){
        if(!dout[i]&& c[i]>0){
            cout << i << ' ' << c[i]<<endl; 
            flag = false;
        }
    }

    if(flag){
        cout << "NULL";
    }

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define N 110
int w[N][N];
int c[N],u[N],in[N];
int inout[N];   //第i个元素为-1表示第i个节点为下一层层的神经元，即输出的目的神经元
                //第i个元素为1表示当前层的神经元
                //第i个元素为0表示该节点的神经元已经输出完了
                //当为3的时候就说明该节点神经元还没有被激活。
                //例如，题目的例子，第一次循环 inout为 {1，1，-1，-1，-1}，第二次为{0，0，1，1，1}.
int n,m;

void exe(bool* flag){
    for(int i=1;i<n+1;i++){
        if(inout[i]==1)
        inout[i]=0;
        if(inout[i]==-1)
        inout[i]=1;
    }

    for(int i=1;i<n+1;i++){
        if(inout[i]==0)
        continue;
        if(in[i]==0){
            if(inout[i]==-1){
                continue;
            }
            inout[i]=1; //input layer
            for(int j=1;j<n+1;j++){
                if(w[j][i]!=0){
                    in[j]--;
                    if(c[i]>0)    //神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为c[i].
                    c[j]+=w[j][i]*c[i];
                    inout[j]=-1;//out layer
                }
            }
        }
    }

    for(int i=1;i<n+1;i++){
        if(inout[i]==-1){
            *flag=true;  //no
            return;
        }
    }
    *flag=false;

}

int main(){
    int i,j,x,y;
    bool flag=true;
    memset(w,0,sizeof(w));
    memset(in,0,sizeof(in));
    cin >> n >> m;
    for(i=1;i<n+1;i++){
        inout[i]=3;
    }
    for(i=1;i<n+1;i++){
        cin >> c[i];
        cin >> u[i];
    }
    for(i=0;i<m;i++){
        cin >> x;
        cin >> y;
        cin >> w[y][x];
    }
    for(i=1;i<n+1;i++){  
        for(j=1;j<n+1;j++){
            if(w[j][i]!=0){
                in[j]++;
            }
        }
    }
    while(flag){
        exe(&flag);
        for(i=1;i<n+1;i++){
            if(inout[i]==-1)
            c[i]-=u[i];
        }
    }

    flag=false;
    for(i=1;i<n+1;i++){
        if(inout[i]==1&& c[i] >0){
        cout<< i <<" "<< c[i]<<endl;
        flag=true;
        }
    }
    if(!flag)
    cout << "NULL";

    return 0;
}