题解 洛谷 Luogu P1038 [NOIP 2003 提高组] 神经网络 拓扑排序 C++
标题传送门
P1038 神经网络 - 洛谷 | 计算机科学教育新生态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/P1038https://csdnimg.cn/release/blog_editor_html/release2.3.7/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=O83Ahttps://www.luogu.com.cn/problem/P1038
思路
为什么用拓扑排序？
拓扑排序的主要应用之一就是基于 DAG (有向无环图) 的信息传递，这也是一种动态规划
本题的话，就是按拓扑序列传递 c * w
具体地说，c += c * w (边的方向为 x >> y)，累加之后减去阈值 u
标题要求分层，所以我们要逐层操作
什么是拓扑排序，怎么求拓扑排序，是很底子的内容，此处不赘述了
坑点
1.输入层不用减去 u，即输入层的 u 完全没用
2.神经元 x 处于高兴状态，即 c > 0 时，信息才会传递到 y
代码
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
constexpr int N = 101;
vector<PII> to, ans;
int from, n, p, c, u, q, head, tail = -1;
void toposort()
{
for (int i = 1; i <= n; ++i)
if (from == 0)
q[++tail] = i;
while (head <= tail)
{
int sz = tail - head + 1;
for (int i = 0; i < sz; ++i) //逐层操作，一次性出队一整层
{
int x = q;
if (tail == n - 1) //到最后一层了，计入答案
{
if (c > 0) ans.emplace_back(x, c);
continue;
}
for (auto& z : to)
{
int X = z.first, w = z.second;
if (c > 0) c += c * w; //只有处于兴奋状态的神经元会传递信息
if (--from == 0)
{
q[++tail] = X;
c -= u; //写在这里就只让新入队的节点减掉阈值，不会让输入层减掉阈值
}
}
}
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> p;
for (int i = 1; i <= n; ++i) cin >> c >> u;
while (p--)
{
int x, y, w;
cin >> x >> y >> w;
to.emplace_back(y, w);
++from;
}
toposort();
if (ans.empty()) { cout << "NULL"; return 0; }
sort(ans.begin(), ans.end()); //答案要求有序
for (auto& z : ans)
cout << z.first << ' ' << z.second << '\n';
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]