题目名称 2266. [HAOI 2016] 食物链
输入输出 chain_2016.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2016-04-24
开放分组 全部用户
提交状态
分类标签
通过:142, 提交:478, 通过率:29.71%
GravatarkZime 100 0.066 s C++
GravatarHeHe 100 0.079 s C++
GravatarHeHe 100 0.080 s C++
GravatarYoungsc 100 0.097 s C++
Gravatar可以的. 100 0.101 s C++
Gravatarzeppoe 100 0.118 s C++
GravatarBennettz 100 0.129 s C++
GravatarHyoi_0Koto 100 0.133 s C++
Gravatarlyqlyqcogs 100 0.133 s C++
Gravatar11101001 100 0.134 s C++
关于 食物链 的讨论
当场10分+1行特判=AC
Gravatar铁策
2016-04-24 13:07 1楼
这题把不吃也不被吃的生物算上食物链20分,否则满分
死于生物没有学好,也不能全怪出题人........
GravatarSatoshi
2016-04-24 13:07 2楼
考场上瞎写暴力的我巧妙避过了生物规律的坑,拿到70....
GravatarFETS 1/3
2016-04-24 14:07 3楼
什么是食物链。。。。。
Gravatar再见
2016-04-24 14:28 4楼
回复 @sherc :
孤立的生物不算食物链.....
GravatarSatoshi
2016-04-24 15:05 5楼
一次AC。嗨森。
我打的是大暴力。
$f[v]$代表以$v$为终点的简单路径的条数。
先toposort。
按topo序枚举终点v,$f[v]=\sum f[u]$
经ck提醒,不是O(NM)而是O(N+M)
GravatarRapiz
2016-04-24 15:44 6楼
回复 @Rapiz : 你复杂度怎么搞的。。。怎么可能$O(nm)$,最多$O(n+m)$吧。。。
Gravatar铁策
2016-04-24 15:35 7楼
回复 @铁策 :
好像是哦……
GravatarRapiz
2016-04-24 15:42 8楼
记忆化搜索,并不明白为什么单个点是符合基本法的,看来文化课学不好OI还是要退役啊
GravatarFmuckss
2016-04-24 19:51 9楼
高一表示并不知道单点不算食物链orz
GravatarCydiater
2016-04-25 13:09 10楼
本来以为考试的时候没加特判,不会AC的,结果后来看我的代码才发现,其实我已经不知不觉加了一个特判…所以成为全场仅有的2个AC的之一…
Gravatar甘罗
2016-04-25 13:34 11楼
Gravatar铁策
2016-05-02 23:01 12楼
其实写的时候用一个else就不必加特判了
GravatarKCkwok
2016-04-25 21:42 13楼
裸搜是过不了的,加个记忆数组即可。记得用邻接表啊
GravatarO(1)
2016-04-28 18:22 14楼
dfs+记忆化,用邻接表存图
Gravatarjjky
2016-10-29 17:25 15楼
orz
GravatarShirry
2017-04-07 19:03 16楼
时隔半个月才a掉。。。之前裸搜t了最后3个点,换了一种搜索顺序(倒序树的遍历)就a掉了。。。。但是这还可以优化。因为还是有重复搜索。。
。。
GravatarkZime
2017-02-03 21:46 17楼
为啥记忆化搜索要比技巧裸搜还要慢。。。难道是递归的锅QAQ
GravatarkZime
2017-02-03 21:59 18楼
woc,刚开始写dp写成“return sum”了,导致记忆化搜索没有卵用.....
GravatarzChengYuan
2017-04-08 17:56 19楼
终于让我过了哈...
GravatarFisher.
2017-04-15 14:12 20楼
3933
Gravatar不需要黄桃
2017-07-08 11:44 21楼
出度和入度都为0的是单个生物
Gravatar@@@
2017-07-09 09:55 22楼
数组开小彩色报错……
GravatarHZOI_蒟蒻一只
2017-08-24 16:05 23楼
数组开小彩色报错……
213题留念(滑稽)
GravatarHZOI_蒟蒻一只
2017-08-24 16:06 24楼
无数人在评论处提醒自己开始自己结束不算一条链,但我一开始写还是忘了这茬。。。尬
GravatarHyoi_0Koto
2017-08-30 15:02 25楼
@4831 同问
GravatarWHZ0325
2018-04-11 12:02 26楼

2266. [HAOI 2016] 食物链

★★   输入文件:chain_2016.in   输出文件:chain_2016.out   简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

如图所示为某生态系统的食物网示意图,据图回答第一小题。

1.数一数,在这个食物网中有几条食物链(   )

现在给你$n$个物种和$m$条能量流动关系,求其中的食物链条数。

物种的名称为从$1$到$n$编号,$m$条能量流动关系形如

$a_1\ b_1$

$a_2\ b_2$

$a_3\ b_3$

$\dots\dots$

$a_{m-1}\ b_{m-1}$

$a_m\ b_m$

其中$a_i\ b_i$表示能量从物种$a_i$流向物种$b_i$。

【输入格式】

第一行两个正整数$n$和$m$。

接下来$m$行每行两个整数$a_i\ b_i$表示$m$条能量流动关系。

(数据保证输入数据符合生物学特点,且不会有重复的能量流动关系出现)

【输出格式】

一个整数即食物网中的食物链条数。

【样例输入】

10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 8
7 6
7 9
8 5
9 8
10 6
10 7
10 9

【样例输出】

9

【样例解释】

就是上面题目描述1的那个图。

各个物种的编号依次为:

草<->1 兔<->2 狐<->3 鼠<->4 猫头鹰<->5 吃虫的鸟<->6 蜘蛛<->7 蛇<->8 青蛙<->9 食草昆虫<->10。

【数据范围】

$1 \leq n \leq 100000,0 \leq m \leq 200000$。

【来源】

HAOI2016上午第一题 部分题面由ck进行调整