题解

#include<bits/stdc++.h>
using namespace std;
int n,w[114514][10086],p;
struct sj{
    int c,u;
} a[54188];
vector<int>In,Out;
bool vis[222];
queue<int>q;
void dfs(int t){
    vis[t]=true;
    bool hasnxt=false;
    for(int i=1;i<=n;++i)
    if(w[t][i]){
        hasnxt=true;
        if(!vis[i])dfs(i);
    }
    if(!hasnxt)Out.push_back(t);
}
void bfs(){
    memset(vis,0,sizeof(vis));
    for(int i=0;i<In.size();++i){
        q.push(In[i]);
        vis[In[i]]=true;
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        bool b=true;
        a[u].c-=a[u].u;
        if(a[u].c>0)
        for(int v=1;v<=n;++v)
        if(w[u][v]){
            a[v].c+=w[u][v]*a[u].c;
            if(!vis[v]){
                vis[v]=true;
                q.push(v);
            }
        }
    }
}
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;++i){
        cin>>a[i].c>>a[i].u;
        if(a[i].c)In.push_back(i);
    }
    memset(w,0,sizeof w);
    while(p--){
        int x,y,z;
        cin>>x>>y>>z;
        w[x][y]=z;
    }
    memset(vis,0,sizeof vis);
    for(int i=0;i<In.size();++i)dfs(In[i]);
    for(int i=0;i<In.size();++i)a[In[i]].u=0;
    bfs();
    bool hasans=false;
    sort(Out.begin(),Out.end());
    for(int i=0;i<Out.size();++i)
    if(a[Out[i]].c>0){
        hasans=true;
        cout<<Out[i]<<' '<<a[Out[i]].c<<'\n';
    }
    if(!hasans) puts("NULL");
    return 0;
}