hust校赛 1615 Matrix 矩阵跟其逆矩阵的乘积中不为0的元素个数

hust校赛 1615 Matrix 矩阵和其逆矩阵的乘积中不为0的元素个数

MatrixTime Limit: 3 Sec  Memory Limit: 128 MB
Submissions: 164  Solved: 38
DescriptionTo efficient calculate the multiplication of a sparse matrix is very useful in industrial filed.Let's consider this problem:A is an N*N matrix which only contains 0 or 1. And we want to know the result of A*AT.Formally, we define B = A*AT, A(i,j) is equal to 1 or 0, and we know the number of  1 in matrix A is MAnd your task is to calculate B.InputThe input contains several test cases. The first line of input contains a integer C indicating the number of the cases.For each test case, the first line contains two integer N and M.and each of next M lines contains two integer X and Y, which means A(x,y) is 1. N <= 100,000 M <= 1000.C <= 10 OutputFor each test case, it should have a integer W indicating how many element in Matrix B isn't zero in one line.Sample Input

25 31 02 13 33 30 01 02 0

Sample Output

39

HINTAT means the Transpose of matrix A, for more details, AT(i,j) = A(j,i).eg:if Matrix A is:1 2 34 5 67 8 9 then the matrix AT is 1 4 72 5 83 6 9Source

The 7th(2012) ACM Programming Contest of HUST
Problem Setter: Zheng Zhang

题意:矩阵A为0,1矩阵，求矩阵B等于A乘以A的逆，然后求B有多少个不等于0的数

思路：

在本子上写几组数据即可发现下面的规律 ：

Problem I: Matrixhttp://acm.hust.edu.cn/problem.php?cid=1106&pid=8/*   题意:矩阵A为0,1矩阵，求矩阵B等于A乘以A的逆，然后求B有多少个1   思路：矩阵乘以矩阵的逆相当于A每行和所有的行相乘。所以，比较矩阵A每列对应有多少个相等的1，         循环A的行，看第i行的每列最大有多少个数"1",就是对应B的第i行的1的个数。但是如果用二维数组         开10000*10000会超内存，而且是1的也最多只有1000个，所以用op数组标记，用row[i][]对应的所有         是1的列存起来，col[]为第j列有多少 个1.然后查找就可以了
*/#include<stdio.h>#include<string.h>int row[1005][1005];int op[100005];int col[100005];int Max(int a,int b){return a>b?a:b;}int main(){int n,m,T,i,x,y,t,sum,w,v;    scanf("%d",&T);while(T--){memset(row,0,sizeof(row));memset(col,0,sizeof(col));memset(op,0,sizeof(op));scanf("%d%d",&n,&m);v=1;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);if(op[x]){w=op[x];             t=++row[w][0];row[w][t]=y;col[y]++;}else{op[x]=v;row[v][1]=y;row[v][0]=1;col[y]++;v++;} }  sum=0;        for(i=1;i<v;i++){x=col[row[i][1]];t=2;while(row[i][t]){                     x=Max(x,col[row[i][t]]);t++;}sum+=x;}printf("%d\n",sum);}return 0;}



 

 

查看更多 下一篇