稀疏矩阵乘法优化

 1 Sec 256 MB |  Markdown 显示标签
33
通过提交

题目描述

给定两个稀疏矩阵 AABB,其中 AAm×km \times k 的矩阵,BBk×nk \times n 的矩阵。请计算它们的乘积矩阵 C=A×BC = A \times B,并输出 CC 的所有非零元素(按行主序排列,同一行按列升序排列)。

稀疏矩阵采用 三元组顺序表(TSMatrix) 存储,格式如下:

  • 每个非零元素用 (行号, 列号, 值) 表示,行号和列号从 0 开始
  • 输入保证矩阵维度合法,且非零元素数量远小于矩阵大小

输入格式

  • 第一行三个整数 m,k,pm, k, p,表示矩阵 AA 的行数、列数和非零元素个数
  • 接下来 pp 行,每行三个整数 row,col,valrow, col, val,表示 AA 的一个非零元素
  • 随后一行三个整数 k,n,qk, n, q,表示矩阵 BB 的行数、列数和非零元素个数
  • 接下来 qq 行,每行三个整数 row,col,valrow, col, val,表示 BB 的一个非零元素

输出格式

  • 第一行输出结果矩阵 CC 的非零元素个数 tt
  • 接下来 tt 行,每行三个整数 row,col,valrow, col, val,表示 CC 的一个非零元素(按行主序排列,同一行按列升序)
  • CC 为零矩阵,仅输出 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

提示

  • 1m,k,n10001 \le m, k, n \le 1000
  • 0p,q1040 \le p, q \le 10^4
  • 保证输入合法,且 AA 的列数等于 BB 的行数
 上传者
coach
 创建时间
2025-03-27 17:17
 修改时间
2025-03-29 16:58