M29740:神经网络

拓扑排序, AI, http://cs101.openjudge.cn/2025springcs201testing/M29740/

随着深度学习技术的发展，神经网络已广泛应用于图像识别、自然语言处理、推荐系统等多个领域。近年来，图神经网络（Graph Neural Networks, GNN）作为一种能够处理非欧式结构化数据的深度学习方法，越来越受到研究者关注。小P同学最近在学习图神经网络的基础知识时，尝试设计了一个简化的“前馈图神经网络”模型，并希望借助编程来验证其推理过程是否合理。

在小P的模型中，一个图神经网络被抽象成一个有向图，图中的节点代表神经元（或计算单元），边则表示信息的传递通道。任意两个节点之间逻辑上至多视为一条有向边。下图是一个神经元节点的示意图：

神经元（编号为 i）

图中，X1 ~ X3 表示来自上游节点的信息输入，Y1 ~ Y2 是向下游节点的输出通道，Ci 表示神经元当前的激活值（activation），而 Ui 是该节点的偏置项（bias），可视为其内在的阈值参数。

神经元按一定的顺序排列，构成整个图神经网络。在小P的模型之中，神经元近似于分层摆放，可以近似视作输入层、若干隐藏层与输出层；信息只能沿有向边由前向后传播。下图是一个最简单的三层神经网络的例子。

现实中若某些突触损坏，会产生“闭环反馈”使整个网络失效。若这幅有向图 存在回路（哪怕仅为自环），称为神经坏死，网络将彻底无法工作。

小P定义的神经元更新规则如下（令 n 表示总神经元数量）：

其中：

Wji 表示从节点 j 到节点 i 的边权重（可以为负值）
Cj 是上游神经元的当前激活值
Ui 是当前神经元的偏置项
若 Ci > 0，则该神经元处于激活（active）状态，下一时刻将以强度Ci 向下一层传递信号；否则，它将保持静默（inactive）

当输入层（入度为0的节点）的神经元激活后，该网络模型将以类似于图神经网络的方式逐层传播信号，最终在输出层（出度为0的节点）产生结果。

输入

输入文件第一行是两个整数 n（1≤n≤100）和 p（0 ≤ p ≤ n(n-1)）。

接下来 n 行，每行 2 个整数，第 i+1 行是神经元 i 最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为 0。

再下面 p 行，每行有两个整数 i,j 及一个整数 Wij，表示连接神经元 i,j 的边权值为 Wij。(i,j) 二元组可重复出现，若重复则视作一条边，将权重累加即可。

输出

输出文件包含若干行，每行有 2 个整数，分别对应一个神经元的编号，及其最后的状态，2 个整数间以空格分隔。仅输出最后状态大于 0 的输出层神经元状态，并且按照编号由小到大顺序输出。

若图中存在任何有向环（神经坏死），或所有输出层神经元最后状态均 ≤0，则输出 NULL。

样例输入

样例输出

样例1：
3 1
4 1
5 1

样例2：
NULL

提示

拓扑排序，AI

输入层神经元状态不需减去其偏置项输入层可以激活也可以不激活，C <= 0 是不激活输入层

C/C++，变量类型需要考虑long long以防止溢出

来源

TA-xjk

python

from collections import defaultdict, deque

n, p = map(int, input().split())
activation = [0] * (n + 1)   # 当前激活值 C_i
bias = [0] * (n + 1)         # 偏置 U_i
in_degree = [0] * (n + 1)    # 入度（拓扑排序用）
out_degree = [0] * (n + 1)   # 出度，用于区分输出层
incoming_sum = [0] * (n + 1) # 用来累加加权输入
graph = defaultdict(list)    # 邻接表：graph[u] 是一个列表，存 (v, w) 表示 u -> v 权重 w

# 读取每个神经元的初始状态和偏置
# 对于非输入层的节点，其初始 activation 一定是 0，题目保证了这一点
for i in range(1, n + 1):
    c, u = map(int, input().split())
    activation[i] = c
    bias[i] = u

# 读取 p 条有向边，直接把每条边 (u -> v, 权重 w) 放进邻接表
# 并维护 in_degree、out_degree
for _ in range(p):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    in_degree[v] += 1
    out_degree[u] += 1

# 拓扑排序队列：所有入度为 0 的节点先入队
queue = deque()
for i in range(1, n + 1):
    if in_degree[i] == 0:
        queue.append(i)

visited_count = 0

# 拓扑排序 + 模拟“前馈图神经网络”的信号传播
while queue:
    u = queue.popleft()
    visited_count += 1

    # 如果当前节点 u 是“激活”状态（activation[u] > 0），才对下游 v 产生影响
    if activation[u] > 0:
        for v, w in graph[u]:
            # 等价于：若存在多条 u->v 边，这里会多次累加 activation[u] * 对应的 w
            incoming_sum[v] += activation[u] * w

            # “剥除”这一条边对 v 的依赖
            in_degree[v] -= 1
            if in_degree[v] == 0:
                # 当 v 的所有前驱都“处理完”后，计算 v 的激活值
                activation[v] = incoming_sum[v] - bias[v]
                if activation[v] <= 0:
                    activation[v] = 0
                queue.append(v)
    else:
        # 如果 u 本身没有激活（activation[u] <= 0），也要让它的所有出边对应的 v 的 in_degree 减 1
        for v, _ in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                activation[v] = incoming_sum[v] - bias[v]
                if activation[v] <= 0:
                    activation[v] = 0
                queue.append(v)

# 如果拓扑排序只处理了 visited_count < n 个节点，就说明图中有环
# （因为有环的节点永远无法把 in_degree 减到 0）
if visited_count < n:
    print("NULL")
else:
    # 遍历所有“输出层”节点（out_degree[i] == 0），只输出 activation[i] > 0 的
    output = []
    for i in range(1, n + 1):
        if out_degree[i] == 0 and activation[i] > 0:
            output.append((i, activation[i]))

    if output:
        # 按编号从小到大输出
        output.sort()
        for idx, val in output:
            print(f"{idx} {val}")
    else:
        # 没有任何一个输出层节点激活值 > 0，也算“无效”输出
        print("NULL")

M29740:神经网络 ​

M29740:神经网络