首页 > 代码库 > SGU196_Matrix Multiplication
SGU196_Matrix Multiplication
给一个无向图，如果第i个点连接第j条边，那么mat[i][j]=1，否则mat[i][j]=0。
求mat的转置乘以本身得到的矩阵每个位置的和是多少？
理解矩阵的意义就比较好做了。
mat[i][j]表示i点可以连接到j边，转置后相乘的意义是第i边和第j边有公共点。
这样，我们只需要统计每个点的度数，这样我们就知道有多少组这样有公共点的边了，也就是最终的答案了。
如果是mat乘以mat的转置，思考的方法也是一样的。
召唤代码君：
#include <iostream>#include <cstring>#include <cstdio>#define maxn 100100typedef long long ll;using namespace std;int d[maxn],n,m,U,V;ll ans;int main(){ scanf("%d%d",&n,&m); ans=m+m; while (m--){ scanf("%d%d",&U,&V); d[U]++,d[V]++; } for (int i=1; i<=n; i++) ans+=ll(d[i])*(d[i]-1); cout<<ans<<endl; return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。