首页 > 代码库 > UVA - 10895 Matrix Transpose

UVA - 10895 Matrix Transpose

2024-07-12 10:00:09   220人阅读

UVA - 10895
Matrix Transpose
Time Limit:3000MS Memory Limit:Unknown 64bit IO Format:%lld & %llu

[Submit]  [Go Back]  [Status]  

Description

Download as PDF


 A: Matrix Transpose 

A matrix is a rectangular array of elements, most commonly numbers. A matrix with$m$ rows and$n$ columns is said to be an$m$-by-$n$ matrix. For example,
\begin{displaymath}A=\pmatrix{1 & 3 & 2 \cr 0 & 4 & -1 \cr 0 & 0 & 0 \cr 5 & -2 & 11}\end{displaymath}

is a 4-by-3 matrix of integers.

The individual elements of a matrix are usually given lowercase symbols and are distinguished by subscripts. The$i$th row and$j$th column of matrix$A$ is usually referred to as$a_{ij}$. For example,$a_{23}=-1$. Matrix subscripts are 1-based.

The transpose of a matrix $M$, denoted$M^T$, is formed by interchanging the rows and columns of$M$. That is, the$ij$th element of$M^T$ is the$ji$th element of$M$. For example, the transpose of matrix$A$ above is:

\begin{displaymath}A^T=\pmatrix{1 & 0 & 0 & 5 \cr 3 & 4 & 0 & -2 \cr 2 & -1 & 0 & 11}\end{displaymath}

A matrix is said to be sparse if there are relatively few non-zero elements. As a$m$-by-$n$ matrix has $mn$ number of elements, storing all elements of a large sparse matrix may be inefficient as there would be many zeroes. There are a number of ways to represent sparse matrices, but essentially they are all the same: store only the non-zero elements of the matrix along with their row and column.

You are to write a program to output the transpose of a sparse matrix of integers.

Input 

You are given several sparse matrix in a row, each of them described as follows. The first line of the input corresponds to the dimension of the matrix,$m$ and$n$ (which are the number of rows and columns, respectively, of the matrix). You are then given$m$ sets of numbers, which represent the rows of the matrix. Each set consists of two lines which represents a row of the matrix. The first line of a set starts with the number $r$, which is the number of non-zero elements in that row, followed by$r$ numbers which correspond to the column indices of the non-zero elements in that row, in ascending order; the second line has $r$ integers which are the matrix elements of that row. For example, matrix$A$ above would have the following representation:
4 3
3 1 2 3
1 3 2
2 2 3
4 -1
0

3 1 2 3
5 -2 11
Note that for a row with all zero elements, the corresponding set would just be one number, `0‘, in the first line, followed by a blank line.

You may assume:

  • the dimension of the sparse matrix would not exceed 10000-by-10000,
  • the number of non-zero element would be no more than 1000,
  • each element of the matrix would be in the range of -10000 to 10000, and
  • each line has no more than 79 characters.

Output 

For each input case, the transpose of the given matrix in the same representation.

Sample Input 

4 3
3 1 2 3
1 3 2
2 2 3
4 -1
0

3 1 2 3
5 -2 11

Sample Output 

3 4
2 1 4
1 5
3 1 2 4
3 4 -2
3 1 2 4
2 -1 11

题意：首先给你n*m的矩阵，然后给出每行的情况。第一个数r代表该行有几个非0的数，位置是哪里，然后给出每个位置的值，求矩阵的倒置

思路：用两个vector，一个记录该列有效值所对应的行，还一个记录该位置的值

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 10010;

vector<int> row[MAXN];
vector<int> val[MAXN];
int n, m, arr[MAXN];

void print() {
	printf("%d %d\n", m, n);	
	for (int i = 1; i <= m; i++) {
		int len = row[i].size();
		printf("%d", len);
		for (int j = 0; j < len; j++)
			printf(" %d", row[i][j]);
		if (len == 0)
			printf("\n\n");
		else {
			printf("\n%d", val[i][0]);
			for (int j = 1; j < len; j++)
				printf(" %d", val[i][j]);
			printf("\n");
		}
	}
}

int main() {
	while (scanf("%d%d", &n ,&m) != EOF) {
		for (int i = 0; i < MAXN; i++) {
			row[i].clear();
			val[i].clear();
		}
		int r, x;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &r);	
			for (int j = 1; j <= r; j++)	
				scanf("%d", &arr[j]);
			for (int j = 1; j <= r; j++) {
				scanf("%d", &x);
				row[arr[j]].push_back(i);
				val[arr[j]].push_back(x);
			}
		}
		print();
	}
	return 0;
}


联系
我们