UVa 10895 - Matrix Transpose

链接

传送门

题意

给出一个稀疏矩阵,输出它的转置矩阵。

思路

三元组储存,排序后输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long LL;
const int maxn = 1010;
int tmp[maxn];
struct Node {
int r, c, v;
bool operator < (const Node& rhs) const {
return r < rhs.r || (r == rhs.r && c < rhs.c);
}
} a[maxn];

int main() {
int n, m;
while (~scanf("%d%d", &n, &m)) {
memset(a, 0, sizeof a);
int tot = 0;
for (int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
for (int j = 0; j < x; ++j) {
scanf("%d", &tmp[j]);
}
for (int j = 0; j < x; ++j) {
scanf("%d", &a[tot].v);
a[tot].c = i + 1, a[tot].r = tmp[j];
++tot;
}
}
sort(a, a + tot);
printf("%d %d\n", m, n);
int p1 = 0, p2 = 0;
for (int i = 1; i <= m; ++i) {
while (a[p2].r == i) {
++p2;
}
printf("%d", p2 - p1);
for (int j = p1; j < p2; ++j) {
printf(" %d", a[j].c);
}
puts("");
for (int j = p1; j < p2; ++j) {
if (j != p1) {
putchar(' ');
}
printf("%d", a[j].v);
}
puts("");
p1 = p2;
}
}
return 0;
}