首页 > 代码库 > 关联矩阵——SGU 196
关联矩阵——SGU 196
对应题目：点击打开链接
Description
Let us consider undirected graph G = which has N vertices and M edges. Incidence matrix of this graph is N * M matrix A = {aij}, such that a ij is 1 if i-th vertex is one of the ends of j-th edge and 0 in the other case. Your task is to find the sum of all elements of the matrix ATA.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
Input
The first line of the input file contains two integer numbers - N and M (2 <= N <= 10 000, 1 <= M <= 100 000). 2M integer numbers follow, forming M pairs, each pair describes one edge of the graph. All edges are different and there are no loops (i.e. edge ends are distinct).
Output
Output the only number - the sum requested.
Sample Input
1
4 4
1 2
1 3
2 3
2 4
Sample Output
18
题意：先理解关联矩阵~，理解之后即求矩阵A的转置矩阵与A相乘所得矩阵的所有元素之和
思路：m[i][j]表示i点可以连接到j边，转置后相乘的意义是第i边和第j边有多少个公共点。
这样，我们只需要统计每个点的度数，从每个点的度数选2个。这样我们就知道有多少组这样有公共点的边了，最后加上2*m（m[i][i]表示一条边，当然连接2个点了），也就是最终的答案了。
如果是mat乘以mat的转置，思考的方法也是一样的。
别人的思路。。。#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
const int MAXN=100000+10;
using namespace std;
int du[MAXN];
int C(int x)
{
if(x<=1) return 0;
return x*(x-1);
}
int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d", &T);
while(T--)
{
memset(du,0,sizeof(du));
int n,m;
scanf("%d%d", &n,&m);
int k=m;
while(k--)
{
int u,v;
scanf("%d%d", &u,&v);
du[u]++;
du[v]++;
}
int ans=0;
for(int i=1; i<=n; i++)
ans+=C(du[i]);
printf("%d\n", ans+2*m);
if(T) printf("\n");
}
return 0;
}
关联矩阵——SGU 196