题解 洛谷 Luogu P1038 [NOIP 2003 提高组] 神经网络 拓扑排序 C++ ...

标题

传送门

P1038 [NOIP 2003 提高组] 神经网络 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/problem/P1038https://www.luogu.com.cn/problem/P1038https://www.luogu.com.cn/problem/P1038https://www.luogu.com.cn/problem/P1038https://www.luogu.com.cn/problem/P1038

https://www.luogu.com.cn/problem/P1038
思路

为什么用拓扑排序？
拓扑排序的主要应用之一就是基于 DAG (有向无环图) 的信息传递，这也是一种动态规划
本题的话，就是按拓扑序列传递 c[x] * w
具体地说，c[y] += c[x] * w (边的方向为 x >> y)，累加之后减去阈值 u
标题要求分层，所以我们要逐层操作
什么是拓扑排序，怎么求拓扑排序，是很底子的内容，此处不赘述了
坑点

1.输入层不用减去 u，即输入层的 u 完全没用
2.神经元 x 处于高兴状态，即 c[x] > 0 时，信息才会传递到 y
代码

1. #include <vector>
2. #include <algorithm>
3. #include <iostream>
4. using namespace std;
5. typedef pair<int, int> PII;
6. constexpr int N = 101;
7. vector<PII> to[N], ans;
8. int from[N], n, p, c[N], u[N], q[N], head, tail = -1;
9. void toposort()
10. {
11.         for (int i = 1; i <= n; ++i)
12.                 if (from[i] == 0)
13.                         q[++tail] = i;
14.         while (head <= tail)
15.         {
16.                 int sz = tail - head + 1;
17.                 for (int i = 0; i < sz; ++i) //逐层操作，一次性出队一整层
18.                 {
19.                         int x = q[head++];
20.                         if (tail == n - 1) //到最后一层了，计入答案
21.                         {
22.                                 if (c[x] > 0) ans.emplace_back(x, c[x]);
23.                                 continue;
24.                         }
25.                         for (auto& z : to[x])
26.                         {
27.                                 int X = z.first, w = z.second;
28.                                 if (c[x] > 0) c[X] += c[x] * w; //只有处于兴奋状态的神经元会传递信息
29.                                 if (--from[X] == 0)
30.                                 {
31.                                         q[++tail] = X;
32.                                         c[X] -= u[X]; //写在这里就只让新入队的节点减掉阈值，不会让输入层减掉阈值
33.                                 }
34.                         }
35.                 }
36.         }
37. }
38. int main()
39. {
40.         ios::sync_with_stdio(0); cin.tie(0);
41.         cin >> n >> p;
42.         for (int i = 1; i <= n; ++i) cin >> c[i] >> u[i];
43.         while (p--)
44.         {
45.                 int x, y, w;
46.                 cin >> x >> y >> w;
47.                 to[x].emplace_back(y, w);
48.                 ++from[y];
49.         }
50.         toposort();
51.         if (ans.empty()) { cout << "NULL"; return 0; }
52.         sort(ans.begin(), ans.end()); //答案要求有序
53.         for (auto& z : ans)
54.                 cout << z.first << ' ' << z.second << '\n';
55.         return 0;
56. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。