Luogu-P1308 神经网络

题面

分析

按照要求拓扑排序即可
代码奉上

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <cstring>
#include <algorithm>
#define rint register int
#define ll long long
using namespace std;
template <typename xxx> inline void read(xxx &x)
{
    int f = 1;x = 0;
    char c = getchar();
    for(; c < '0' || c > '9' ; c = getchar()) if(c=='-') f = -1;
    for(;'0' <= c && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    x *= f;
}
template <typename xxx> inline void print(xxx x)
{
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x > 9) print(x/10);
    putchar(x % 10 + '0');
}
const int inf = 0x7fffffff;
const int maxn = 100100;
const int mod = 1e9+7;
int n,m;
struct edge{
    int to,last;
    ll val;
}e[maxn];
int head[maxn],tot;
inline void add(int from,int to,ll val) {
    ++tot;
    e[tot].to = to;
    e[tot].val = val;
    e[tot].last = head[from];
    head[from] = tot;
}
ll ci[maxn],ui[maxn];
int in[maxn],out[maxn];
int ans[maxn],top;
queue<int>q;
int main()
{
    read(n);read(m);
    for(rint i = 1; i <= n; ++i) {
        read(ci[i]);read(ui[i]);
    }
    for(rint i = 1; i <= m; ++i) {
        ll x,y,z;
        read(x);read(y);read(z);
        add(x,y,z);++in[y];++out[x];
    }
    for(rint i = 1;i <= n; ++i) {
        if(!in[i]&& ci[i] > 0) q.push(i);
        if(!out[i]) ans[++top] = i;//从小到大记录输出层
    }
    while(q.size()) {
        int x = q.front();q.pop();
        for(rint i = head[x];i;i = e[i].last) {
            --in[e[i].to];
            ci[e[i].to] += e[i].val * ci[x];//这里之前搞了一个tem[]代替ci但莫名其妙WA了 
            if(!in[e[i].to]) {
                ci[e[i].to] -= ui[e[i].to];
                if(ci[e[i].to] > 0) {
                    q.push(e[i].to);
                }
            }
        }
    }
    int mk = 1;
    for(rint i = 1;i <= top; ++i) {
        if(ci[ans[i]]) {
            mk = 0;
            break;
        }
    }
    if(mk) printf("NULL\n");
    else {
        for(rint i = 1;i <= top; ++i) {
            if(ci[ans[i]] > 0) printf("%lld %lld\n",ans[i],ci[ans[i]]);//仅输出最后状态“大于”0的输出层神经元状态，并且按照编号由小到大顺序输出,WA一个点 
        }
    }
    return 0;
}
/*
*/

Luogu-P1308 神经网络

原文：https://www.cnblogs.com/Thomastine/p/11738301.html