洛谷 P1038 [NOIP2003 提高组] 神经网络（拓扑排序）

题目传送门

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

解题思路

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

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

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

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

代码

#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);elsec[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;
}