Matrix Multiplication
Time Limit: 2000/1000MS (Java/Others)Memory Limit: 128000/64000KB (Java/Others)
Problem Description
Let us consider undirected graph G = {V; E} which has N vertices and M edges. Incidence matrix of this graph is N × M matrix A = {ai,j}, such that ai,j 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.
edge and 0 in the other case. Your task is to find the sum of all elements of the matrix ATA.
Input
The first line of the input file contains two integer numbers — N and M (2 ≤ N ≤ 10 000, 1 ≤ M ≤100 000). Then 2*M 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).
and there are no loops (i.e. edge ends are distinct).
Output
Output the only number — the sum requested.
Sample Input
4 4 1 2 1 3 2 3 2 4
Sample Output
18
Source
Andrew Stankevich Contest 1
Manager
mathlover
显然矩阵太大无法存, 所以要找规律,这题特殊在矩阵是关联矩阵,看图
所以,C[i][j]可以看成是第k行里任意两个元素相乘的和
由于这里的矩阵是01矩阵,所以可以只考虑1 * 1,显然,第k行的和就是点k的度
比如第k行为 1 0 1 1,任意2个元素相乘的和是9,deg[k]^2 == 9
#include<map> #include<set> #include<list> #include<stack> #include<queue> #include<vector> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int deg[10010]; int main() { int n, m; while (~scanf("%d%d", &n, &m)) { memset( deg, 0, sizeof(deg) ); int u, v; for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); deg[u]++; deg[v]++; } long long ans = 0; for (int i = 1; i <= n; i++) { ans += (long long)(deg[i] * deg[i]); } printf("%lld\n", ans); } return 0; }