• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

SGU 196 – Matrix Multiplication

POJ解题 第四度 10年前 (2010-09-01) 46次浏览 0个评论 扫描二维码

file

Let us consider an undirected graph G = <V, E> 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 给定一个有N个顶点,M条边的图,N M的矩阵A中的元素a(i,j)为1当且仅当第i个顶点是第j条边的端点,否则为零。求A\’A的各个元素之和。

直接计算的话,内存不够,时间也不够(O(N^3)).考虑到最终求的是和,可以用类似POJ 3318 的压缩方法来处理.设A\’A=C, 构造一个全一向量I,最终结果是IA\’A=IC各个元素之和.这样,O(N^2)的时间就可解决,但是在0.5秒之内依然不可能运行一亿次,考虑到矩阵是稀疏的,再观察矩阵构造方法,就可以得到O(M*2)的算法,这里不再叙述,可参考代码.

#include <stdio.h>
int a[10005]={0};
int b[100005][2];
int main()
{
    int n,m;
    int ans=0;
    int x,y,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        b[i][0]=x;
        b[i][1]=y;
        a[x]++;
        a[y]++;
    }

    for(i=1;i<=m;i++)
    {
        ans+=a[b[i][0]]+a[b[i][1]];
    }
    printf("%dn",ans);
    return 0;
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1022.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址