思路与算法

对图拓扑排序。入度为0的输入点保留给定状态，其余点累计值初始化为负阈值。某点所有前驱处理完后，若累计值≤0就把有效状态设为0，否则将该正状态乘各出边权累加到后继。最后按编号输出正状态的汇点。

正确性说明

按拓扑顺序归纳。输入点按定义具有给定有效状态。处理任一非输入点时，所有前驱已正确计算并且各贡献恰累加一次，所以其累计值正是前驱加权和减阈值；钳制0恰实现平静点不传信号的规则。故全部有效状态正确，筛选汇点得到所需输出。

复杂度

初始化顶点与入度O(n)，读边与拓扑传播O(n+p)，输出O(n)，总O(n+p)时间和O(n+p)空间。

易错点

不扣输入点阈值，不能以初始C非0代替入度判定输入层。负累计状态不能乘负边继续传播。按有效正状态输出；孤立输入点也是输出点。累加用64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m))
        return 0;
    vector<long long> c(n), u(n);
    for (int i = 0; i < n; i++)
        cin >> c[i] >> u[i];
    vector<vector<pair<int, int>>> g(n);
    vector<int> d(n);
    for (int i = 0, a, b, w; i < m; i++) {
        cin >> a >> b >> w;
        --a;
        --b;
        g[a].push_back({b, w});
        d[b]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (!d[i])
            q.push(i);
        else
            c[i] = -u[i];
    }
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        c[v] = max(0LL, c[v]);
        for (auto e : g[v]) {
            c[e.first] += c[v] * e.second;
            if (!--d[e.first])
                q.push(e.first);
        }
    }
    bool any = false;
    for (int i = 0; i < n; i++)
        if (g[i].empty() && c[i] > 0) {
            cout << i + 1 << ' ' << c[i] << '\n';
            any = true;
        }
    if (!any)
        cout << "NULL\n";
}