Codeforces 489D Unbearable Controversy of Being

最新推荐文章于 2025-02-11 18:07:34 发布

月黑风高叶

最新推荐文章于 2025-02-11 18:07:34 发布

阅读量380

点赞数

分类专栏： Codefores 文章标签： ACM codeforces

本文链接：https://blog.csdn.net/csdn364988181/article/details/49129447

版权

Codefores 专栏收录该内容

34 篇文章

订阅专栏

题目链接：http://codeforces.com/problemset/problem/489/D

题意：给出n点，m条有向边，问有多少个如下图的菱形

$\text{[math]}$

思路：枚举2点，以及与第一个点的边，若是该边的终点与第二个点相连，则第一个点和第二个点有一条菱形边，算出2点间所有的菱形边则可以求出有多少个菱形，看起来时间复杂度是o(n*n*m)但是用了vecter动态数组，其实就是枚举n个点以及m条边复杂度书o(n*m)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxn 3030
using namespace std;

int G[maxn][maxn];
vector <int> link[maxn];


int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(G,0,sizeof(G));
        memset(link,0,sizeof(link));
        for (int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u][v]=1;
            link[u].push_back(v);
        }

        int res=0;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                if (i==j) continue;
                int sum=0;
                for (int k=0;k<link[i].size();k++)
                {
                    int v=link[i][k];
                    if (G[v][j]==1) sum++;
                }
                res+=sum*(sum-1)/2;
            }
        }
        printf("%d\n",res);
    }
}