对于一个有向无环图（DAG），我们要找出一种顶点的排序方式，使得对于图中任意 u,vu, v ，如果 u,vu, v 之间有一条 uu 指向 vv 的有向路，则 uu 排在 vv 的前面。这种排序方式被称为拓扑排序（Topological sorting）。

下图是一个DAG：

WfjVIS.png

2,1,3,5,4,62, 1, 3, 5, 4, 6 是其一个拓扑排序。

模板题

题目

P1038 [NOIP2003 提高组] 神经网络

背景

人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。

题目描述

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：

每条边有一个权值，输入点有一个初始权值 C[i]C[i] ，非输入点有一个阈值 U[i]U[i] ，每个非输入点的 C[i]=∑j→iC[j]>0C[j]×wi,jC[i] = \displaystyle\sum_{j \to i}^{C[j] > 0} C[j] \times w_{i,j} ，输出所有输出节点中 C[i]C[i] 值大于等于 00 的值。

输入格式

第一行两个整数 n,mn, m ，表示点数和边数。

接下来 nn 行表示每个节点的初始 C[i], U[i]C[i], \ U[i] 值。

最后 mm 行每行三个整数 u,v,wu, v, w ，表示从 uu 指向 vv 权值为 ww 的边。

输出格式

输出输出节点的编号及其大于等于 00 的 C[i]C[i] 值。

如果没有，则输出 NULL 。

输入输出样例

输入

1
2
3
4
5
6
7
8
9
10
11
12
5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1

输出

1
2
3
3 1
4 1
5 1

说明/提示

解决方案

思路

题目实际是一道模拟题，按顺序从输入节点逐层模拟神经网络的前向传播即可。不幸的是，只给出点的邻接关系不足以让我们执行这样的模拟操作，我们需要先对节点进行拓扑排序。

拓扑排序的算法的流程描述非常简洁：

  1. 找出图中入度为 00 的点，将其放入已排好的序列末尾。
  2. 删除与与该点相关的所有边。
  3. 重复上述过程。

显然，这个过程可以开一个队列来实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 110;
int n, m, cc, cnt;
int head[maxn], C[maxn], U[maxn], indegree[maxn], outdegree[maxn], topo[maxn];
queue<int> q;
struct Node
{
    int to, w, next;
} G[maxn * maxn];

void addedge(int u, int v, int w)
{
    ++cc;
    G[cc].to = v;
    G[cc].w = w;
    G[cc].next = head[u];
    head[u] = cc;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &C[i], &U[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addedge(u, v, w);
        indegree[v]++;
        outdegree[u]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!indegree[i])
        {
            q.push(i);
            U[i] = 0;
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        topo[++cnt] = u;
        C[u] -= U[u];
        for (int i = head[u]; i; i = G[i].next)
        {
            int v = G[i].to;
            int w = G[i].w;
            indegree[v]--;
            if (C[u] > 0)
            {
                C[v] += w * C[u];
            }
            if (!indegree[v])
                q.push(v);
        }
    }
    bool flag = true;
    for (int i = 1; i <= n; i++)
    {
        if (!outdegree[i] && C[i] > 0)
        {
            flag = false;
            printf("%d %d\n", i, C[i]);
        }
    }
    if (flag)
    {
        printf("NULL");
    }
    return 0;
}