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之间输出一个空行。

贴个代码纪念下。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const int N =  + ;

 LL A[N], ans;

 int main()

 {

     int T, n, m, v1, v2;

     while (scanf("%d", &T) != EOF)

     {

         while (T--)

         {

             int maxi = -;

             scanf("%d%d", &n, &m);

             memset(A, , sizeof(A));

             for (int i = ; i <= m; i++)

             {

                 scanf("%d%d", &v1, &v2);

                 A[v1]++;    // 算出每个点连着多少条边

                 A[v2]++;

                 int tm = max(v1, v2);

                 maxi = max(maxi, tm);   // 求出最大那个点的编号

             }

             ans = ;

             for (int i = ; i <= maxi; i++)

             {

                 if (A[i])

                     ans += A[i] * A[i];

             }

             printf("%lld\n", ans);

             if (T)

                 puts("");

         }

     }

     return ;

 }

巴特西

zoj 2316 Matrix Multiplication 解题报告

最新文章

热门文章