违规紫衫,问私有题
  • 板块灌水区
  • 楼主glass_goldfish
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/9/14 20:10
  • 上次更新2024/9/14 22:10:19
查看原帖
违规紫衫,问私有题
1328469
glass_goldfish楼主2024/9/14 20:10

小蓝的火车

题目背景

小蓝切水题切的起劲,这时信息老师走了过来(你为什么不珍惜上课时间!竟敢切水题!#%#%@$#)...
小蓝被罚做一道题。

题目描述

L 城有 nn 个火车站和 mm 条铁路(直达)。第 ii 条铁路的开始地点为 aia_i,结束地点为 bib_i(所有道路均为单向)。老师让小蓝求出,一共有多少不同的铁路(可以经过若干条直达铁路)。

形式化题意

给出一个 nn 个点,mm 条边,每条边开始为 aia_i,结束为 bib_i(单向边),求出: i=1nj=1nf(i,j)\sum_{i=1}^{n}\sum_{j=1}^{n}f(i,j) 其中,f(i,j)f(i,j) 代表从 iijj 有多少条不同的路径(当且仅当路径长度不同或经过的任意一条边不同,保证没有重边,但是可能有 ap=bq,aq=bpa_p=b_q,a_q=b_p),特别的,如果 i=ji=j,那么 f(i,j)=0f(i,j)=0

输入格式

第一行两个整数 n,mn,m
接下来 mm 行,每行两个整数 ai,bia_i,b_i

输出格式

仅一行一个整数,表示答案。

样例 #1

样例输入 #1

2 1
1 2

样例输出 #1

1

提示

【数据范围】
对于 100%100\% 的数据,1n,m,ai,bi1001\le n,m,a_i,b_i\le100。 数据见此D题,有没有人会啊

2024/9/14 20:10
加载中...