题目传送门

感觉这道题需要我们高超的语文阅读水平……

解题思路

我们发现要计算一个细胞的状态值（），就需要先算出有边指向它的其他细胞对答案的贡献；

这是有拓扑序的，所以我们想到拓扑排序。

题目中说了，我们要从  的点开始进行拓扑排序，然后把它指向的细胞的贡献加上即可（就是拓扑排序的板子）。

注意，起点不要减掉阈值（本题最坑人的地方）。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p;
int c[101],u[101];
int rd[101],cd[101];
struct edge{
	int to,w;
};
vector<edge> g[101];
void tuopu()
{
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		if(c[i]>0)
			q.push(i);
		else
			c[i]-=u[i];
	}
	
	while(!q.empty())
	{
		int x=q.front();
		//c[x]-=u[x];
		q.pop();
		for(auto y:g[x])
		{
			rd[y.to]--;
			if(c[x]>0)
				c[y.to]+=y.w*c[x];
			if(rd[y.to]==0)
			{
				q.push(y.to);
			}
		}
	}
}
vector<pair<int,int> > ans;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i]>>u[i];
	}
	int u,v,w;
	for(int i=1;i<=p;i++)
	{
		
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		rd[v]++;
		cd[u]++;
	}
	
	tuopu();
	bool bj=0;
	for(int i=1;i<=n;i++)
	{
		if(cd[i]==0)
		{
			if(c[i]>0)
			{
				bj=1;
				ans.push_back(make_pair(i,c[i]));
			}
		}
	}
	if(bj)
	{
		for(auto y:ans)
		{
			cout<<y.first<<" "<<y.second<<endl;
		}
	}
	else{
		cout<<"NULL";
	}
	return 0;
}