P1038 神经网络(拓扑排序)

传送门

思路：一道拓扑排序经典题，此题要求算出最后所有的结点$c[i]$。

一开始$c[i]>0$的点被认为是输入层,即入度为0的点。然后用拓扑排序对相邻结点不断操作即可，输出层即出度为0的点。最后从$1$到$n$遍历判断该结点是否满足$!out[i]\&\&c[i]>0$即可。这里$out[i]$也可以用链式前向星中的$h[i]$判断。

时间复杂度：$O(n+m)$

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+5;
#define mst(a) memset(a,0,sizeof a)
struct edge{
	int to,nt,w;
}e[N<<1];
int n,m,in[N],h[N],cnt,c[N];
queue<int>q;
void add(int u,int v,int w){
	e[++cnt].to=v,e[cnt].w=w;
	e[cnt].nt=h[u];
	h[u]=cnt;
}
void toposort(){
	while(q.size()){
		int u=q.front();q.pop();
		if(c[u]>0){
			for(int i=h[u];i;i=e[i].nt){
				 int v=e[i].to,w=e[i].w;
				 c[v]+=c[u]*w;
				 in[v]--;
				 if(!in[v]) q.push(v);
			}
		}
		else {
			for(int i=h[u];i;i=e[i].nt){
				int v=e[i].to;
				 in[v]--;
				 if(!in[v]) q.push(v);
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u;i<=n;i++){
		scanf("%d%d",&c[i],&u);
		if(c[i]>0)  q.push(i);//输入层 
		else c[i]-=u;
	}
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		in[v]++;
	}
	toposort();
	int f=0;
	 for(int i=1;i<=n;i++){
	 	 if(!h[i]&&c[i]>0){ //h[i]==0等价于出度为0 
	 	 	f=1;
	 	 	printf("%d %d\n",i,c[i]);
		  }
	 }
	 if(!f) puts("NULL");
	return 0;
}