# 稀疏矩阵乘法优化算法题面 ## 题目名称 稀疏矩阵乘法优化 **时间限制**：1秒 **内存限制**：256MB --- ## 题目描述 给定两个稀疏矩阵 $A$ 和 $B$，其中 $A$ 是 $m \times k$ 的矩阵，$B$ 是 $k \times n$ 的矩阵。请计算它们的乘积矩阵 $C = A \times B$，并输出 $C$ 的所有非零元素（按行主序排列，同一行按列升序排列）。 稀疏矩阵采用 **三元组顺序表（TSMatrix）** 存储，格式如下： - 每个非零元素用 `(行号, 列号, 值)` 表示，行号和列号从 **0** 开始 - 输入保证矩阵维度合法，且非零元素数量远小于矩阵大小 --- ## 输入格式 - 第一行三个整数 $m, k, p$，表示矩阵 $A$ 的行数、列数和非零元素个数 - 接下来 $p$ 行，每行三个整数 $row, col, val$，表示 $A$ 的一个非零元素 - 随后一行三个整数 $k, n, q$，表示矩阵 $B$ 的行数、列数和非零元素个数 - 接下来 $q$ 行，每行三个整数 $row, col, val$，表示 $B$ 的一个非零元素 --- ## 输出格式 - 第一行输出结果矩阵 $C$ 的非零元素个数 $t$ - 接下来 $t$ 行，每行三个整数 $row, col, val$，表示 $C$ 的一个非零元素（按行主序排列，同一行按列升序） - 若 $C$ 为零矩阵，仅输出 `0` --- ## 数据范围 - $1 \le m, k, n \le 1000$ - $0 \le p, q \le 10^4$ - 保证输入合法，且 $A$ 的列数等于 $B$ 的行数