设为首页 加入收藏

TOP

UVA - 10895 Matrix Transpose
2015-07-20 18:06:49 来源: 作者: 【大 中 小】 浏览:12次
Tags：UVA 10895 Matrix Transpose
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, andeach 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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int MAXN = 10010; vector
       
         row[MAXN]; vector
        
          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; }



【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU 4085 斯坦纳树 下一篇：链表（二）――单向链表的基本操..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: