Problem G: Matrix

Time Limit: 2 Sec   Memory Limit: 128 MB

Submit: 80  
Solved: 11

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 AA
T.

Formally, we define B = AA
T, Aij 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 Axyis 1.

N ≤ 100000, 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

25 31 02 13 33 30 01 02 0

Sample Output

39

HINT

 

A
Tmeans the Transpose of matrix A, for more details, A
Tij= Aji.

eg:

if Matrix A is:

123

456

789

then the matrix ATis

147

258

369

思路：这个题真是做了好久，虽然不是很难，但想法的不同的确会影响做题的结果。

还有就是开始的时候题目数据有点水，后来改了数据就没能通过，又做了好久才搞出来。

我把这个过程的经历都说一下：

题目的意思就是求一个矩阵（元素为1或0）乘以它的转置矩阵，求结果矩阵的元素有多少个不为0，因为数据比较大（100000），直接用数组保持是不现实的，并且也不能运算。开始想到一种方法，实质上b[i][j]=a矩阵的第i行*第j行，而由矩阵的乘法

b[i][j]=a[i][k]*a'[k][j]+…

也就是说k值相等的情况下，如果a[i][k]与a'[k][j]都为1,那么b[i][j]一定不为0

例如

原矩阵   0 0          0 0 矩阵逆

             1 0          0 1

             2 1          1 2

k值相等，可以看出是0或1，当为0时，可以得出（0 0）（1 1）这两个元素不为0，当为1时，（2 2）不为0

但这样会有重复的现象，如


原矩阵   0 0          0 0 矩阵逆

             0 1          1 0

             2 1          1 2

这样得出的点有（0 0）（0 0）（0 2）（2 2）

出现了计算重复的点，必须把这些点减去

于是，出现了下面的代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 1000
int x[MAX+10],y[MAX+10];
int main()
{
     //freopen("in.txt", "r", stdin);
   //freopen("out.txt", "w", stdout);
	int num,i,j,n,m,ans;
	scanf("%d",&num);
	while(num--)
	{
	       scanf("%d%d",&n,&m);
		   for(i=0;i<m;i++)
                 scanf("%d %d",&x[i],&y[i]);
		   sort(x,x+m);
		   sort(y,y+m);
		   ans=0;
		   for(i=1;i<m;i++)//减去重复的
           {
			   if(x[i]==x[i-1])
                    ans--;
           }
		   for(i=0;i<m;i++)
			   for(j=0;j<m;j++)
				   if(y[i]==y[j])
                        ans++;
		   printf("%d
",ans);
	}

	return 0;
}


提交的时候是过了，但后来发现还有重复的，如

原矩阵   3 1          1 3 矩阵逆

             3 2          2 3

             5 1          1 5

             5 2          2 5

点（3 5）和（5 3）重复了，但不是上面那种形式的重复。

于是改了数据，于是…这种方法就做不了了。

下面说另一种思路，只加，但没有重复的

用MAP做就很简单了。。。。。。。

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<algorithm>
using namespace std;
struct node
{
    int x,y;
}p[1010];
map <int,int> mymap;
int cmp(node a,node b)
{
    return a.x<b.x;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int t,n,m,i,j,k,u,ans,cont;
    scanf("%d",&t);
    int line[1010];
    while (t--)
    {
        memset(line,0,sizeof(line));
        cont=0;ans=0;
        scanf("%d%d",&n,&m);
        for (i=0;i<m;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        sort(p,p+m,cmp);
        for(i=1;i<m;i++)
            if(p[i].x!=p[i-1].x)
                line[++cont]=i;//第i行在line中开始的位置
        for(i=0;i<=cont;i++)//一共有cont行
        {
            mymap.clear();
            for(j=line[i];j<(i==cont?m:line[i+1]);j++)
                mymap[p[j].y]=1;
            for(k=0;k<=cont;k++)
                for(u=line[k];u<(k==cont?m:line[k+1]);u++)
                    if(mymap.find(p[u].y)!=mymap.end())
                    {
                        ans++;
                        break;//不考虑重复的
                    }
        }
        printf("%d
",ans);
    }
    return 0;
}