M23555: 节省存储的矩阵乘法

implementation, matrices, http://cs101.openjudge.cn/practice/23555

要求用节省内存的方式实现，不能还原矩阵的方式实现。

思路：利用STL容器思路，对矩阵Y采用行优先的存储方式，实现稀疏矩阵的存储与计算，本题难度可以接受，算上思考时间使用20分钟左右。

#include <iostream>
#include <vector>
#include <map>
#include <tuple>

using namespace std;

int main() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;

    vector<tuple<int, int, int>> X;
    for (int i = 0; i < m1; ++i) {
        int row, col, val;
        cin >> row >> col >> val;
        X.emplace_back(row, col, val);
    }

    vector<vector<pair<int, int>>> Y_rows(n);
    for (int i = 0; i < m2; ++i) {
        int row, col, val;
        cin >> row >> col >> val;
        Y_rows[row].emplace_back(col, val);
    }
    map<pair<int, int>, int> Z;
    for (const auto& x : X) {
        int i = get<0>(x);    
        int k = get<1>(x);    
        int a = get<2>(x);    
        for (const auto& y : Y_rows[k]) {
            int j = y.first;  
            int b = y.second; 
            Z[{i, j}] += a * b;
        }
    }
    for (const auto& entry : Z) {
        if (entry.second != 0) {
            cout << entry.first.first << " " << entry.first.second << " " << entry.second << endl;
        }
    }
    return 0;
}