Codeforces Round #277.5 (Div. 2)-D「建议收藏」

Codeforces Round #277.5 (Div. 2)-D

大家好,又见面了,我是全栈君。

题意:求该死的菱形数目。直接枚举两端的点。平均意义每一个点连接20条边,用邻接表暴力计算中间节点数目,那么中间节点任选两个与两端可组成的菱形数目有r*(r-1)/2.

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a,x) memset(a,x,sizeof a)
typedef long long LL;
using namespace std;

const int mod=1e9 +7;
const int maxn=3005;
const int maxm=30005;

int first[maxn],nex[maxm],v[maxm],ecnt,g[maxn][maxn];

void add_(int a,int b)
{
    v[ecnt]=b;
    nex[ecnt]=first[a];
    first[a]=ecnt++;
}
int main()
{
    int n,m,x,y;
    while(~scanf("%d%d",&n,&m))
    {
        memset(first,-1,sizeof first);ecnt=0;
        memset(g,0,sizeof g);
        for(int i=0;i<m;i++)
            scanf("%d%d",&x,&y),add_(x,y),g[x][y]=1;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
           for(int j=1;j<=n;j++)
           if(i!=j){
               int r=0;
               for(int e=first[i];~e;e=nex[e])
               if(g[v[e]][j])r++;
               ans+=r*(r-1)/2;
           }
        }
        printf("%d\n",ans);
    }
    return 0;
}

D. Unbearable Controversy of Being
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Tomash keeps wandering off and getting lost while he is walking along the streets of Berland. It’s no surprise! In his home town, for any pair of intersections there is exactly one way to walk from one intersection to the other one. The capital of Berland is very different!

Tomash has noticed that even simple cases of ambiguity confuse him. So, when he sees a group of four distinct intersections abc and d, such that there are two paths from a to c — one through b and the other one through d, he calls the group a “damn rhombus”. Note that pairs (a, b)(b, c)(a, d)(d, c) should be directly connected by the roads. Schematically, a damn rhombus is shown on the figure below:


Codeforces Round #277.5 (Div. 2)-D「建议收藏」

Other roads between any of the intersections don’t make the rhombus any more appealing to Tomash, so the four intersections remain a “damn rhombus” for him.

Given that the capital of Berland has n intersections and m roads and all roads are unidirectional and are known in advance, find the number of “damn rhombi” in the city.

When rhombi are compared, the order of intersections b and d doesn’t matter.

Input

The first line of the input contains a pair of integers nm (1 ≤ n ≤ 3000, 0 ≤ m ≤ 30000) — the number of intersections and roads, respectively. Next m lines list the roads, one per line. Each of the roads is given by a pair of integers ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi) — the number of the intersection it goes out from and the number of the intersection it leads to. Between a pair of intersections there is at most one road in each of the two directions.

It is not guaranteed that you can get from any intersection to any other one.

Output

Print the required number of “damn rhombi”.

Sample test(s)
input
5 4
1 2
2 3
1 4
4 3

output
1

input
4 12
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

output
12

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115961.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 滴滴的大数据可视化效果「建议收藏」

    滴滴的大数据可视化效果「建议收藏」前言上一篇专门针对mobike的空间可视化效果写了一篇总结,本篇主要基于滴滴的大数据可视化做一个描述,上篇介绍的空间可视化效果偏静态的,滴滴的大数据可视化更加动态,形式上也更加丰富多彩,本篇主要参考了这篇文章:http://baijiahao.baidu.com/s?id=1588178807086352632和《滴滴出行2017年度城市交通出行报告》。蝌蚪图通过“蝌蚪图”,滴滴大数据…

  • python随机产生数字_随机数生成excel

    python随机产生数字_随机数生成excel使用场景:随机短信验证码importrandomimportstring#指定随机数长度r_num=4#生成数字+字母(字符串序列)token=string.ascii_letters+string.digits”’string.ascii_letters:生成大小写字母(type:字符串)string.digits:生成数字…

  • Navicat 15 for MySQL手动激活码_通用破解码

    Navicat 15 for MySQL手动激活码_通用破解码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 极值点,驻点,拐点的关系_求驻点

    极值点,驻点,拐点的关系_求驻点极值点极值点:一阶导数发生变号的点,对于导数不存在的点,分析其左导数和右导数的正负是否相同,相同则不是极值点;若不同则为极值点。极值点是该点的x坐标值,而极值是该点对应的y坐标值。驻点驻点:只是单纯地符合f’(xo)=0的点,导数不存在的点不是驻点。拐点拐点:二阶导数发生变号的点,对于二阶导数不存在的点,分析其左二阶导数和右二阶导数的正负是否相同,相同则不是拐点;若不同则是拐点。常用结论:1.只要f’(xo)=0,那么该点就是驻点。2.若f’(xo)=0,而f”(xo)≠0,该点一定是极值点

    2022年10月29日
  • java voliate_voliate关键字及其示例

    java voliate_voliate关键字及其示例voliate关键字1使变量在线程间可见对于避免不可见性问题,Java还提供了一种弱形式的同步,即使用了volatile关键字。该关键字确保了对一个变量的更新对其他线程可见。当一个变量被声明为volatile时候,线程写入时候不会把值缓存在寄存器或者或者在其他地方,当线程读取的时候会从主内存重新获取最新值,而不是使用当前线程的拷贝内存变量值。volatile虽然提供了可见性保证,但是不能使用他来…

  • c# mysql executenonquery_c#数据四种执行方法(ExecuteNonQuery)—–转载「建议收藏」

    c# mysql executenonquery_c#数据四种执行方法(ExecuteNonQuery)—–转载「建议收藏」c#数据四种执行方法(ExecuteNonQuery)1.使用ExecuteReader()操作数据库2.使用ExecuteNonQuery()操作数据库3.使用ExecuteScalar()操作数据库4.使用DataSet数据集插入记录,更新数据一、使用ExecuteReader()操作数据库,执行查询操作的非常好的方法。ExecuteReader比DataSet而言,DataReader具有较…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号