首页 > 代码库 > acdeream Matrix Multiplication

acdeream Matrix Multiplication

2024-07-27 05:28:09   218人阅读

D - Matrix Multiplication

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

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.

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).

Output

      Output the only number — the sum requested.

Sample Input

4 41 21 32 32 4

Sample Output

18

 1 /* 2 * this code is made by 987690183 3 * Problem: 1213 4 * Verdict: Accepted 5 * Submission Date: 2014-10-14 13:40:27 6 * Time: 236MS 7 * Memory: 1716KB 8 */ 9 #include<iostream>10 #include<stdio.h>11 #include<cstring>12 #include<cstdlib>13 using namespace std;14  15 int num[10002];16 long long get(int n,int m)/**Cn,m**/17 {18     long long sum = 1;19     for(int i=1,j=n;i<=m;i++,j--)20         sum=sum*j/i;21     return sum;22 }23 int main()24 {25     int n,m,x,y;26     int hxl=  0;27     while(scanf("%d%d",&n,&m)>0)28     {29         memset(num,0,sizeof(num));30         for(int i=1;i<=m;i++)31         {32             scanf("%d%d",&x,&y);33             num[x]++;34             num[y]++;35             hxl = hxl+2;36         }37         long long tom = hxl;38         for(int i=1;i<=10000;i++)39         if(num[i]>=2)40         {41             tom=tom+get(num[i],2)*2;42         }43         printf("%lld\n",tom);44     }45     return 0;46 }

 



acdeream Matrix Multiplication


联系
我们