思路

看到有关入度出度的问题很容易想到用\(toposort\)来做，这个题想起来非常的简单，但是坑点不少。

读入时的阈值\(u\)其实如果\(c > 0\)（可以传递信息时）直接减去就行，不会有影响，这取决于那个\(sigma\)的写法，\(u\)没有和任何一个数相乘，只是简单的累加，所以一开始直接减去就好。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 105
#define MAXM 10010
typedef long long ll;
int n, p, res;
int head[MAXN], cnt;
int in[MAXN], out[MAXN];
struct input{
    int c, u;
} a[MAXN];
struct node{
    int nxt, to, val;
} edge[MAXM << 1];
inline int read(void){
    int f = 1, x = 0;char ch;
    do{ch = getchar();if(ch=='-')f = -1;} while (ch < '0' || ch > '9');
    do{ x = (x << 1) +(x << 3) + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
    return f * x;
}
inline void add_edge(int x,int y,int z){
    ++cnt;
    edge[cnt].nxt = head[x];
    edge[cnt].to = y;
    edge[cnt].val = z;
    head[x] = cnt;
    return;
}
std::queue<int> Q;
void toposort(void){
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for (int i = head[u]; i;i=edge[i].nxt){
            int v = edge[i].to;
            --in[v];
            if(a[u].c>0) a[v].c += a[u].c * edge[i].val;
            if(!in[v]) Q.push(v);
        }
    }
}
int main(){
    n = read(), p = read();
    for (int i = 1; i <= n;++i){
        a[i].c = read(), a[i].u = read();
        if(a[i].c) Q.push(i);
        else a[i].c -= a[i].u;
    }
    for (int i = 1; i <= p;++i){
        int u = read(), v = read(), w = read();
        add_edge(u, v, w), ++out[u], ++in[v];
    }
    toposort();
    bool ck = 0;
    for (int i = 1; i <= n;++i)
        if(a[i].c>0&&(!out[i])) printf("%d %d\n", i, a[i].c), ck = 1;
    if(!ck) puts("NULL");
    return 0;
}