SGU - 196 - Matrix Multiplication （矩陣乘法）
196. Matrix Multiplication
time limit per test: 0.25 sec.
memory limit per test: 65536 KB input: standard
output: standard
Let us consider an undirected graph G =
which has N vertices and M edges. Incidence matrix of this graph is an N × M matrix A = {aij}, such that aij 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 where AT is A transposed, i.e. an M × N matrix obtained from A by turning its columns to rows and vice versa.
Input
The first line of the input file contains two integer numbers — N and M (2 le N le 10,000, 1 le M le 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 test(s)
Input
4 4 1 2 1 3 2 3 2 4 Output
18
[submit] [forum]
Author:
Andrew Stankevich, Georgiy Korneev
Resource:
Petrozavodsk Winter Trainings 2003
Date:
2003-02-06
思路：自己手動執行幾下就可以發現規律，這裡存儲圖中邊的方法為完全關聯矩陣（離散數學中有介紹），而本題的規律為只要統計每個定點的出現次數的平方即可
AC代碼：
#include
#include
#include
#include
#define LL long long
using namespace std;
int num[10005];
int N, M;
int main() {
while(scanf("%d %d", &N, &M) != EOF) {
memset(num, 0, sizeof(num));
for(int i = 0; i < M; i++) {
int a, b;
scanf("%d %d", &a, &b);
num[a]++, num[b]++;
}
LL ans = 0;
for(int i = 1; i <= N; i++) {
ans += (num[i] * num[i]);
}
cout << ans << endl;
}
return 0;
}
