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 AAT.
Formally, we define B = AAT, 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
2
5 3
1 0
2 1
3 3
3 3
0 0
1 0
2 0
Sample Output
3
9
HINT
ATmeans the Transpose of matrix A, for more details, ATij= 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\n",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\n",ans);
}
return 0;
}
