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)
blank

相关推荐

  • Node.js

    Node.js

  • Element.clientWidth属性

    Element.clientWidth属性内联元素以及没有CSS样式的元素的clientWidth属性值为0。Element.clientWidth属性表示元素的内部宽度,以像素计。该属性包括内边距padding,但不包括边框border、外边距margin和垂直滚动条(如果有的话)。intElemClientWidth是一个整数,表示元素的clientWidth。clientWidth是一个只读属性。…

  • 论文投稿系列之Cover Letter写法(一)[通俗易懂]

    论文投稿系列之Cover Letter写法(一)[通俗易懂]论文投稿系列之CoverLetter写法(一)研之成理微信公众号:研之成理(ID:rationalscience)取消关注PytLab酱等87人赞同了该文章作者:ZSH1.什么是Coverletter?CoverLetter,即投稿信,是论文投递时与论文一起发送给编辑的信件,其目的是让编辑在阅读你的论文之前,简单了解你文章的基本情况。Cove…

  • 算法练习之DP 求LCM (最长公共子序列)

    算法练习之DP 求LCM (最长公共子序列)

  • 跨境物流报关流程_跨境电商海关备案流程

    跨境物流报关流程_跨境电商海关备案流程  国际社会物流报关的基本工作流程有哪些?  报关是指货物、行李、邮递物品和运输工具进出境时,所有人或者其代理人应当将规定的文件、证件报海关查验。要求海关办理有关进出口手续。    二、清关:是指货物所有人履行企业相关国家法定权利义务,海关对货物放行。    海关登记和年检:指进出口单位向所在地海关申报登记,取得报关单位资格的程序。    四、外关区备案、年审:指已在该单位价值所在关区办理了报关企业注册信息登记相关手续的报关工作单位,为取得从其它关区口岸贸易进出口商品货物的报关资格.

  • DVWA登录出现allow_url_fopen = On allow_url_include = On的错误

    DVWA登录出现allow_url_fopen = On allow_url_include = On的错误进入到DVWA页面中:点击下图中按钮Creat/ResetDatabase创建数据库:出现如下错误提示:CouldnotconnecttotheMySQLservice.Pleasechecktheconfigfile.12意思是:无法连接到MySQL服务。请检查你的config文件。问题解决此时我们找到config文件下的config.inc.php文件打开进行操作,将$DVWA[‘db_password’]改为和phpstudy_pro中数据

发表回复

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

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