SGU - 196 - Matrix Multiplication （矩阵乘法） - c++编程基础

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 = {a _ij}, 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 A ^TA where A ^T 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; }