ITSA 54 - [Problem 4] 稀疏矩陣相乘 - 參考答案

Difficulty: Eazy
Ref: ITSA 54 - [Problem 4] 稀疏矩陣相乘

/*******************************************************/
/* [Problem 4] 稀疏矩陣相乘                             */
/* Author: awei0905  [at]  awei0905.blogspot.tw        */
/* Version: 2017/05/16                                 */
/*******************************************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main() {
 int n;
 scanf("%d", &n);
 while (n--) {
  int m, v, row, col, val, matrix[11][11] = { 0 };
  scanf("%d %d", &m, &v);
  for (int i = 0; i < v; i++) {
   scanf(" (%d:%d)=%d", &row, &col, &val);
   matrix[row][col] = val;
  }

  for (int i = 1; i <= m; i++) {
   int j = 0;
   while (j < i - 1)
    printf("%d ", matrix[j++][i]);

   matrix[i - 1][++j] = 0;
   for (int k = 1; k <= m; k++)
    matrix[i - 1][j] += matrix[i][k] * matrix[j][k];

   while (j < m) {
    printf("%d ", matrix[i - 1][j]);
    matrix[i - 1][++j] = 0;
    for (int k = 1; k <= m; k++)
     matrix[i - 1][j] += matrix[i][k] * matrix[j][k];
   }
   printf("%d\n", matrix[i - 1][j]);
  }
 }
}

Debug： I/O
此稀疏矩陣又是方陣，所以 A*AT 處理起來相對簡單。
A*AT 又是 Symmetric Matrix，所以有避開重複計算。

1
10 10
(3:2)=3
(2:3)=2
(1:2)=2
(7:2)=3
(8:5)=1
(10:1)=2
(5:9)=2
(9:6)=3
(4:7)=2
(6:6)=3

4 0 6 0 0 0 6 0 0 0
0 4 0 0 0 0 0 0 0 0
6 0 9 0 0 0 9 0 0 0
0 0 0 4 0 0 0 0 0 0
0 0 0 0 4 0 0 0 0 0
0 0 0 0 0 9 0 0 9 0
6 0 9 0 0 0 9 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 9 0 0 9 0
0 0 0 0 0 0 0 0 0 4