2815: [ZJOI2012]灾难 - BZOJ
题目描述 Description
阿米巴是小强的好朋友。
阿米巴和小强在草原上捉蚂蚱。小强突然想,如果蚂蚱被他们捉灭绝了,那么吃蚂蚱的小鸟就会饿死,而捕食小鸟的猛禽也会跟着灭绝,从而引发一系列的生态灾难。
学过生物的阿米巴告诉小强,草原是一个极其稳定的生态系统。如果蚂蚱灭绝了,小鸟照样可以吃别的虫子,所以一个物种的灭绝并不一定会引发重大的灾难。
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系:
一个食物网有N个点,代表N种生物,如果生物x可以吃生物y,那么从y向x连一个有向边。
这个图没有环。
图中有一些点没有连出边,这些点代表的生物都是生产者,可以通过光合作用来生存; 而有连出边的点代表的都是消费者,它们必须通过吃其他生物来生存。
如果某个消费者的所有食物都灭绝了,它会跟着灭绝。
我们定义一个生物在食物网中的“灾难值”为,如果它突然灭绝,那么会跟着一起灭绝的生物的种数。
举个例子:在一个草场上,生物之间的关系是:
如果小强和阿米巴把草原上所有的羊都给吓死了,那么狼会因为没有食物而灭绝,而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以,羊的灾难值是1。但是,如果草突然灭绝,那么整个草原上的5种生物都无法幸免,所以,草的灾难值是4。
给定一个食物网,你要求出每个生物的灾难值。
输入描述 Input Description
第一行是一个正整数N,表示生物的种数。生物从1标号到N。
接下来N行,每行描述了一个生物可以吃的其他生物的列表,格式为用空格隔开的若干个数字,每个数字表示一种生物的标号,最后一个数字是0表示列表的结束。
输出描述 Output Description
包含N行,每行一个整数,表示每个生物的灾难值
样例输入 Sample Input
5
0
1 0
1 0
2 3 0
2 0
样例输出 Sample Output
4
1
0
0
0
数据范围及提示 Data Size & Hint
对50%的数据,N ≤ 10000。
对100%的数据,1 ≤ N ≤ 65534。
输入文件的大小不超过1M。保证输入的食物网没有环。
对于一个点i,他的死亡应该被一系列点影响(就是j死了i就会死),这些点就是这个点i往下走的必经之点
这些点构成一条链,所以可以用前缀和的思想来累加,所以我们只要求出这个点链的next是什么
所以现在关键是求这next
然后我就用了lca来求next
每个点向他的next连一条边,一个点的next就是他的儿子的最近公共祖先
const
maxn=;
maxm=;
var
d,ans,first,dep:array[..maxn]of longint;
last,next:array[..maxm]of longint;
f:array[..maxn,..]of longint;
n,tot:longint; procedure insert(x,y:longint);
begin
inc(d[y]);
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
end; var
q:array[..maxn]of longint;
l,r:longint; procedure init;
var
i,x:longint;
begin
read(n);
for i:= to n do
begin
read(x);
while x<> do
begin
insert(i,x);
read(x);
end;
end;
l:=;
for i:= to n do
if d[i]= then
begin
inc(r);
q[r]:=i;
end;
end; procedure new(x:longint);
var
i:longint;
begin
i:=;
while f[x,i]<> do
begin
f[x,i+]:=f[f[x,i],i];
inc(i);
end;
end; procedure swap(var x,y:longint);
var
t:longint;
begin
t:=x;x:=y;y:=t;
end; function lca(x,y:longint):longint;
var
k:longint;
begin
if dep[x]<dep[y] then swap(x,y);
while dep[x]>dep[y] do
x:=f[x,trunc(ln(dep[x]-dep[y])/ln())];
if x=y then exit(x);
while f[x,]<>f[y,] do
begin
k:=;
while f[x,k+]<>f[y,k+] do
inc(k);
x:=f[x,k];
y:=f[y,k];
end;
exit(f[x,]);
end; procedure work;
var
i,j,t:longint;
begin
while l<=r do
begin
for i:=l to r do
begin
j:=first[q[i]];
while j<> do
begin
dec(d[last[j]]);
if d[last[j]]= then
begin
inc(r);
q[r]:=last[j];
end;
j:=next[j];
end;
end;
l:=i+;
end;
for i:=n downto do
begin
j:=first[q[i]];
t:=last[j];
j:=next[j];
while j<> do
begin
t:=lca(t,last[j]);
j:=next[j];
end;
f[q[i],]:=t;
dep[q[i]]:=dep[t]+;
new(q[i]);
end;
for i:= to n do
inc(ans[f[q[i],]],ans[q[i]]+);
for i:= to n do
writeln(ans[i]);
end; begin
init;
work;
end.
最新文章
- 18 行 JS 代码编一个倒时器
- Python for Infomatics 第13章 网页服务一(译)
- css样式表分类、选择器分类、css基础样式
- UVA-10652 (凸包)
- lintcode:合并排序数组
- Add Two Numbers - C++链表操作
- 《Linux Device Drivers》第十四章 Linux 设备型号
- 1.Google Chrome浏览器 控制台全解析
- SecureCRT 5.2.2版本下载和注册码
- [20171206]rman与truncate2.txt
- xStream转换XML、JSON
- Kafka send问题
- maven私服配置
- p2p手机绑定
- Code::Blocks之自动打开上次未关闭工作空间
- 《剑指offer》---丑数
- APUE(3)---文件I/O (1)
- C语言100例01 PHP版(练习)
- SpringMVC学习 -- 使用 @RequestMapping 映射请求
- bzoj 1061 志愿者招募 费用流
热门文章
- Oracle学习笔记1:win7 x64下安装Oracle10g
- Activity之间传递数据或数据包Bundle,传递对象,对象序列化,对象实现Parcelable接口
- 模仿Word中组织结构图的特点生成流程图
- 【iOS基础学习随笔-1】-基于对象的程序设计
- ACCESS的System.Data.OleDb.OleDbException: INSERT INTO 语句的语法错误
- Matlab摄像头标定得出的参数保存为xml
- 将n(0<;=n<;=10000)的阶乘分解质因数,求其中有多少个m
- C++ Sets
- C++ Priority Queues(优先队列) and C++ Queues(队列)
- 使用kyototycoon挂载leveldb,映射内存磁盘的使用心得