稀疏矩阵乘法优化
1 Sec 256 MB | Markdown
3 | 3 |
通过 | 提交 |
题目描述
给定两个稀疏矩阵 和 ,其中 是 的矩阵, 是 的矩阵。请计算它们的乘积矩阵 ,并输出 的所有非零元素(按行主序排列,同一行按列升序排列)。
稀疏矩阵采用 三元组顺序表(TSMatrix) 存储,格式如下:
- 每个非零元素用
(行号, 列号, 值)
表示,行号和列号从 0 开始 - 输入保证矩阵维度合法,且非零元素数量远小于矩阵大小
输入格式
- 第一行三个整数 ,表示矩阵 的行数、列数和非零元素个数
- 接下来 行,每行三个整数 ,表示 的一个非零元素
- 随后一行三个整数 ,表示矩阵 的行数、列数和非零元素个数
- 接下来 行,每行三个整数 ,表示 的一个非零元素
输出格式
- 第一行输出结果矩阵 的非零元素个数
- 接下来 行,每行三个整数 ,表示 的一个非零元素(按行主序排列,同一行按列升序)
- 若 为零矩阵,仅输出
0
样例输入 #1
3 3 5 0 0 1 0 2 2 1 2 3 2 0 4 2 2 5 3 2 3 0 1 1 1 0 2 2 1 3
样例输出 #1
3 0 1 7 1 1 9 2 1 19
提示
- 保证输入合法,且 的列数等于 的行数