拓扑序

神经网络 (nowcoder.com)

拓扑序，输入层找入度为0的，输出层找出度为0的即可。注意当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。中间层即使c小于等于0也是可以遍历的，而不是当入度为0时判断是否大于零再入队，优先级不一样。

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;

// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second

typedef long long LL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 21;
int e[N], ne[N], h[N],idx; // 链式前向星
int c[N], u[N], w[N], jl[N]; // C U jl -- jl 是 \sum(Ci * Wi)
int in[N]; // 入度 输入层
bool vis[N];
int out[N]; // 出度 输出层
void inpfile();
void add(int u, int v, int a) { // 建图
    e[idx] = v, ne[idx] = h[u], w[idx] = a, h[u] = idx++;
}
/**
in: 
6 8
1 0
1 0
1 100
0 1
0 -2
0 0
1 4 1
2 4 0
3 4 -1
1 5 1
2 5 -1
3 5 -1
4 6 1
5 6 1

out:
6 1

*/
void solve() {
    memset(h, -1, sizeof(h));
    int n, p; 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,a; cin>>u>>v>>a; add(u,v,a);
        in[v]++;
        out[u]++;
    }
    queue<int> q;
    for(int i = 1; i <= n; ++i) {
        if(c[i]) q.push(i), vis[i] = 1;
    }
    while(q.size()) {
        auto tmp = q.front(); q.pop();
        for(int i = h[tmp]; ~i; i = ne[i]) {
            int y = e[i];
            in[y]--; // 入度--
            if(c[tmp] > 0) // c大于0才有作用
                jl[y] += w[i] * c[tmp];
            if(!in[y]) { // 入度为0，进队
                jl[y] -= u[y];
                q.push(y);
                c[y] = jl[y]; // 最终c
            }
        }
    }
    bool fg = false; // 判读是否有输出层大于0的
    for(int i = 1; i <= n; ++i) {
        if( out[i] == 0 && c[i] > 0) fg = true;
    }
    if(!fg) {
        cout<<"NULL";
        return ;
    }
    for(int i = 1; i <= n; ++i) {
        if(!out[i] && c[i] > 0) cout<<i<<" "<<c[i]<<endl;
    }
}
int main()
{
    #ifdef Multiple_groups_of_examples
    int T; cin>>T;
    while(T--)
    #endif
    solve();
    return 0;
}
void inpfile() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}