[NOIP 2003 提高组] 神经网络

题意

题目给了一张分层有向图，每个点是一个神经元。

输入层神经元的当前状态 C[i] 已经给出
非输入层神经元有阈值 U[i]
边 j -> i 有权值 W[j][i]

当一个神经元最终状态 C[i] > 0 时，它才会向后继传递强度为 C[i] 的信号。

要求求出所有输出层神经元（也就是出度为 0 的点）最后的状态；只输出状态大于 0 的输出层。如果一个都没有，就输出 NULL。

样例图

这张图把样例中的网络结构画出来：

digraph G {
  rankdir=LR;
  1 [label="1\nC=1"];
  2 [label="2\nC=1"];
  3 [label="3\nU=1"];
  4 [label="4\nU=1"];
  5 [label="5\nU=1"];
  1 -> 3 [label="1"];
  1 -> 4 [label="1"];
  1 -> 5 [label="1"];
  2 -> 3 [label="1"];
  2 -> 4 [label="1"];
  2 -> 5 [label="1"];
}

点 3,4,5 都会收到来自 1 和 2 的贡献 1 + 1 = 2，再减去自己的阈值 1，所以最后状态都变成 1。

思路

先看一个按定义递归求值的小数据版本：

cpp

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
80
81
82
83// brute.cpp：小数据直接按定义递归求值，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n, m;
long long init_c[MAXN];
long long u_[MAXN];
int indeg[MAXN], outdeg[MAXN];

struct Edge {
    int from;
    long long w;
};

vector<Edge> pre[MAXN];
bool vis[MAXN];
long long memo[MAXN];

// 直接按定义求神经元 u 的最终状态。
long long dfs(int u) {
    if (vis[u]) {
        return memo[u];
    }
    vis[u] = true;

    if (indeg[u] == 0) {
        memo[u] = init_c[u];
        return memo[u];
    }

    long long sum = -u_[u];
    for (Edge e : pre[u]) {
        long long val = dfs(e.from);
        if (val > 0) {
            sum += val * e.w;
        }
    }

    memo[u] = sum;
    return memo[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> init_c[i] >> u_[i];
        pre[i].clear();
        indeg[i] = 0;
        outdeg[i] = 0;
        vis[i] = false;
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        pre[v].push_back({u, w});
        indeg[v]++;
        outdeg[u]++;
    }

    bool has_answer = false;
    for (int i = 1; i <= n; i++) {
        if (outdeg[i] == 0) {
            long long val = dfs(i);
            if (val > 0) {
                cout << i << ' ' << val << '\n';
                has_answer = true;
            }
        }
    }

    if (!has_answer) {
        cout << "NULL\n";
    }

    return 0;
}

这个版本直接按题意去算某个点的最终状态：

如果它是输入层，状态就是给定的 C[i]
如果它不是输入层，先从 -U[i] 开始
然后枚举所有前驱 j
只有当 j 的最终状态大于 0 时，才加上 W[j][i] * C[j]

正式做法不必真的递归，因为题目已经保证图是分层的，也就是一张 DAG。

于是可以按拓扑序模拟整个传播过程：

统计每个点的入度和出度。
对所有非输入层，先把 C[i] 改成 C[i] - U[i]。在本题数据里，非输入层初始 C[i] 通常是 0，所以这一步等价于先设成 -U[i]。
把所有入度为 0 的点入队。
依次弹出点 u：
- 如果 C[u] > 0，说明它处于兴奋状态，就把 C[u] * W[u][v] 加到每个后继 v 上
- 无论它是否兴奋，这条边都算处理过，所以都要给后继入度减一
最后扫描所有出度为 0 的点，输出状态大于 0 的那些。

这里最容易错的地方只有一个：平静状态的神经元不会继续传信号。

代码

cpp

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
long long c[MAXN];   // c[i] : 神经元 i 当前状态
long long u_[MAXN];  // u_[i] : 神经元 i 的阈值
int outdeg[MAXN];

struct Edge {
    int to;
    long long w;
};

vector<Edge> graph[MAXN];
int indeg[MAXN];

void read_input() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> u_[i];
        graph[i].clear();
        indeg[i] = 0;
        outdeg[i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        indeg[v]++;
        outdeg[u]++;
    }

    // 输入层的状态已经直接给出，只有非输入层需要先减去阈值。
    for (int i = 1; i <= n; i++) {
        if (indeg[i] > 0) {
            c[i] -= u_[i];
        }
    }
}

void solve() {
    queue<int> q;
    int deg[MAXN];
    memcpy(deg, indeg, sizeof(indeg));

    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (Edge e : graph[u]) {
            int v = e.to;

            // 只有兴奋状态的神经元才会向后传递信号。
            if (c[u] > 0) {
                c[v] += c[u] * e.w;
            }

            deg[v]--;
            if (deg[v] == 0) {
                q.push(v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    bool has_answer = false;
    for (int i = 1; i <= n; i++) {
        if (outdeg[i] == 0 && c[i] > 0) {
            cout << i << ' ' << c[i] << '\n';
            has_answer = true;
        }
    }

    if (!has_answer) {
        cout << "NULL\n";
    }

    return 0;
}

复杂度

设点数为 n，边数为 m。

每个点入队出队一次
每条边只被扫描一次

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。

总结

这题本质不是复杂 DP，而是 DAG 上的顺序模拟。识别出“分层有向图 + 只从上一层到下一层传递”以后，直接按拓扑序把状态往后推就行。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[NOIP 2003 提高组] 神经网络

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析