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

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

Matrix

Time Limit: 3 Sec Memory Limit: 128 MB
Submissions: 164 Solved: 38

Description

To 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 M

And your task is to calculate B.

Input

The 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

Output

For each test case, it should have a integer W indicating how many element in Matrix B isn't zero in one line.

Sample Input

Sample Output

3
9

HINT

AT means the Transpose of matrix A, for more details, AT(i,j) = A(j,i).

eg:

if Matrix A is:

1 2 3

4 5 6

7 8 9

then the matrix AT is

1 4 7

2 5 8

3 6 9

Source

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

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

思路：

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

#include<stdio.h>
#include<string.h> 
#include<algorithm>
using namespace std;
int x[1000+10],y[1000+10];
int main()
{
	int cas,i,j,n,m,xx,yy,cnt;
	scanf("%d",&cas);
	while(cas--)
	{
	       scanf("%d %d",&n,&m);
		   for(i=0;i<m;i++)
		   {
                 scanf("%d %d",&xx,&yy);
                 x[i]=xx;
				 y[i]=yy;
		   }
		   sort(x,x+m);
		   sort(y,y+m);
		   cnt=0;
		   for(i=1;i<m;i++)
			   if(x[i]==x[i-1]) cnt--;
		   for(i=0;i<m;i++)
		   {
			   for(j=0;j<m;j++)
				   if(y[i]==y[j]) cnt++;
		   }
		   printf("%d\n",cnt);
	}
	
	return 0;
}

同学的解题报告：

Problem I: Matrix

http://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;
}