拓扑排序练习

• 整理的一道模板题：（借鉴的大佬们的，本菜菜细节真的不太行）
• P1038 [NOIP2003 提高组] 神经网络 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：

• 首先建立一张邻接表，然后开两个数组，一个记录出度，一个标记数组，利用队列，只有一开始入度>0,且神经元活跃的点才能传给下一个，即阈值是大于0的， 队列就是正常拓扑排序的模板，记录每个神经元的状态活跃值，最后输出时，注意需要输出神经元活跃的点并且出度为0的点即可，如果都不活跃就输出NULL。

代码如下：

#include
#include 
#include 
#include 
#include
using namespace std;
const int N = 40000;
struct node1 {
	int to;
	int v;
	int next;
} egde[N];
int n, m;
int x, y, w;
int t, h, U;
int c[N];
int head[N];
int chudu[N];//记录出度为0的点
int vis[N];
queue  q;
int cnt = 0, flag = 0;
void add(int u, int v, int w)
{
	cnt++;
	egde[cnt].to = v;
	egde[cnt].v = w;
	egde[cnt].next = head[u];
	head[u] = cnt;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		vis[i] = 0;
		chudu[i] = 0;
		cin >> c[i] >> U;
		if (c[i] > 0)
		{
			q.push(i); 
			vis[i] = 1;
		}
		else {
			c[i] -= U;
		}
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y >> w;
		add(x,y,w);
		chudu[x] = 1;
	}
	while (!q.empty())
	{
		h = q.front(); 
		q.pop();
		if (c[h] <= 0) continue;
		for (int i = head[h]; i; i = egde[i].next)
		{
			t = egde[i].to;
			c[t] += egde[i].v * c[h];
			if (!vis[t])
			{
				q.push(t);
				vis[t] = 1;
			}
		}
	}
	for (int i = 1; i <= n; i++)
		if (!chudu[i] && c[i] > 0)
		{
			cout << i << " " << c[i] << endl;
			flag = 1;
		}
	if (!flag) {
		cout << "NULL" << endl;
	}
}