矩阵转置

三元组形式

struct Node {
    int r, c, val;  // 行、列、值
};

存矩阵三元组的三元组是有序的，按r值递增，再按c值递增。

如何更好地保证转置后的矩阵依然有序?

一个显然的做法是先全部转置，再排序，复杂度大概\(O(nlogn)\)。

还有一个\(O(n)\)的做法：

使用数组\(cnt[]\)，使得\(cnt[i]\)表示转置前的三元组的 \(c == i\) 的\(Node\)的数量。复杂度\(O(n)\)

再使用数组\(pos[]\)，使得 \(pos[i]\) 表示转置前的三元组的 \(c == i\) 的 \(Node\) 应该在转置后的三元组的位置。复杂度\(O(n)\)。

这样就可以在\(O(n)\)的时间内完成。

int n;
vector<Node> OLD(n),NEW(n);
vector<int> cnt(n),pos(n);

// 求cnt
for (int i = 0;i < n;i++) {
    cnt[OLD[i].c]++;
}
// 求pos
pos[0] = 0;
for (int i = 1;i < n;i++) {
    pos[i] = pos[i - 1] + cnt[i - 1];
}
// 求NEW
for (int i = 0;i < n;i++) {
    swap(OLD[i].r, OLD[i].c);
    NEW[pos[OLD[i].r]] = OLD[i];
    pos[OLD[i].r]++;
}

矩阵相乘

给出俩个有序的三元组矩阵\(A\)和\(B\)，求相乘后的矩阵\(C\)。

对\(A\)的每一个值\(x\)，在\(B\)中找到每一个\(y\)，使得 \(x.c = y.r\) ，然后值相乘。

如果\(C\)中没有\(r == x.r c == y.c\)的节点，就将{\(x.r,y.c,x.val * y.val\)}放入C中。

否则，将这个节点的值再加\(x.val * y.val\)。