首页 > 代码库 > zoj 2316 Matrix Multiplication 解题报告
zoj 2316 Matrix Multiplication 解题报告
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2316
题目意思:有 N 个 点,M 条 边。需要构造一个N * M 大小的矩阵A。对于 (i, j) 这个坐标点它表示,对编号为 i 这个点编号为 j 的 点与它相连,此时标记(i, j) 为1,如果坐标点没有跟这条 j 的边相连,就标记为0。构造完这个矩阵A之后,需要求出它的转置矩阵AT,算出 ATA 的和。
新学期第一场比赛!刚开始真是打算直接做的,但是数据太大了, 2 <= N <= 10 000, 1 <= M <= 100 000,只能通过观察来简化,最后做了3个多小时,终于想出来了= =!大感动!专门补了下矩阵的知识......
规律真的需要手动算下才能发现的!!!后来还犯了个低级错误,忘记清空了。每个Test 都需要啦。最后就是格式问题。每个output之间输出一个空行。
贴个代码纪念下。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 typedef long long LL; 8 const int N = 10000 + 2; 9 10 LL A[N], ans;11 12 int main()13 {14 int T, n, m, v1, v2;15 while (scanf("%d", &T) != EOF)16 {17 while (T--)18 {19 int maxi = -1;20 scanf("%d%d", &n, &m);21 memset(A, 0, sizeof(A));22 for (int i = 1; i <= m; i++)23 {24 scanf("%d%d", &v1, &v2);25 A[v1]++; // 算出每个点连着多少条边26 A[v2]++;27 int tm = max(v1, v2); 28 maxi = max(maxi, tm); // 求出最大那个点的编号29 }30 ans = 0;31 for (int i = 1; i <= maxi; i++)32 {33 if (A[i])34 ans += A[i] * A[i];35 }36 printf("%lld\n", ans);37 if (T)38 puts("");39 }40 }41 return 0;42 }
zoj 2316 Matrix Multiplication 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。