BZOJ_2815_[ZJOI2012]灾难 倍增lca + 构造

题意:

我们用一种叫做食物网的有向图来描述生物之间的关系:一个食物网有N个点,代表N种生物,如果生物x可以吃生物y,那么从y向x连一个有向边。这个图没有环。图中有一些点没有连出边,这些点代表的生物都是生产者,可以通过光合作用来生存; 而有连出边的点代表的都是消费者,它们必须通过吃其他生物来生存。如果某个消费者的所有食物都灭绝了,它会跟着灭绝。我们定义一个生物在食物网中的“灾难值”为,如果它突然灭绝,那么会跟着一起灭绝的生物的种数。

给定一个食物网,你要求出每个生物的灾难值。

分析:

按照图中给出的图的拓扑序插点,对于每个点,让能吃它的所有点的lca作为它的父亲

统计一下子树大小就是答案

代码:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 700000 int head[N],to[N<<1],nxt[N<<1],cnt;
int n,m,c[N],Q[N],l,r,f[N][21],dep[N];
int pos[N],siz[N];
int too[N],nxtt[N],headd[N]; inline void add(int u,int v){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
} inline void adda(int u,int v){
too[++cnt]=v;nxtt[cnt]=headd[u];headd[u]=cnt;
} int lca(int x,int y){
int i;
if(dep[x]<dep[y])swap(x,y);
for(i=20;i>=0;i--){
if(dep[f[x][i]]>=dep[y])x=f[x][i];
}
if(x==y)return x;
for(i=20;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
} void dfs(int x,int y){
siz[x]=1;
int i; for(i=head[x];i;i=nxt[i]){
if(to[i]!=y){
dfs(to[i],x);
siz[x]+=siz[to[i]];
}
}
} int main(){
scanf("%d",&n); int i,j,x; for(i=1;i<=n;i++){
for(scanf("%d",&x);x;scanf("%d",&x)){
adda(x,i);c[i]++;
}
} cnt=0; dep[n+1]=1;
for(i=1;i<=n;i++){
if(!c[i]){
Q[r++]=i;
dep[i]=1;
add(i,n+1);
add(n+1,i);
dep[i]=2;
f[i][0]=n+1;
for(j=1;j<=20;j++){
f[i][j]=f[f[i][j-1]][j-1];
}
}
}
while(l<r){
x=Q[l++]; for(i=headd[x];i;i=nxtt[i]){
c[too[i]]--;
if(!pos[too[i]]){
pos[too[i]]=x;
}else{
pos[too[i]]=lca(pos[too[i]],x);
}
if(!c[too[i]]){
add(too[i],pos[too[i]]);
add(pos[too[i]],too[i]);
dep[too[i]]=dep[pos[too[i]]]+1;
f[too[i]][0]=pos[too[i]]; for(j=1;j<=20;j++){
f[too[i]][j]=f[f[too[i]][j-1]][j-1];
} Q[r++]=too[i];
}
}
} //printf("%d\n",root);
//for(i=1;i<=n;i++)if(dep[i]==1)dfs(i,0);
dfs(n+1,0); for(i=1;i<=n;i++){
printf("%d\n",siz[i]-1);
}
}

最新文章

  1. 关于css清除浮动,解决内容溢出的问题
  2. MVC4 学习备忘
  3. iOS开发UI篇—无限轮播(循环展示)
  4. Collection(数组、字典、集合)
  5. wcf通过webHttpBinding方式发布rest web服务
  6. 对RESTful Web API的理解与设计思路
  7. MVC—WebAPI(调用、授权)
  8. sublime插件(配合nodejs环境)
  9. Template - Strategy
  10. [HAOI 2010]软件安装
  11. mysql binlog格式
  12. Java equals()方法和hashCode()方法
  13. Linux extmail的邮件服务器搭建
  14. (大数取模)Big Number hdu1212
  15. VMware14安装centos7
  16. Java获取路径(getResource)
  17. Async方法死锁的问题 Don&#39;t Block on Async Code(转)
  18. 共享锁&amp;排它锁 || 乐观锁&amp;悲观索
  19. 解决 ASP.NET 编辑错误&quot;CS0006: 未能找到元数据文件C:\WINDOWS\assembly\GAC_32\System.EnterpriseServices\2.0.0.0__b03f5f7f11d50a3a\System.EnterpriseServices.dll&quot;
  20. linuxGDB下动态链接库的调试

热门文章

  1. package.json字段全解
  2. 移动web前端开发时注意事项(转)
  3. 微信小程序弹出和隐藏遮罩层动画以及五星评分
  4. Java编程语言下Selenium驱动各个浏览器代码
  5. 安装VirtualBox后 不能选择64bit的系统
  6. Java Selenium 定位元素 实现的一个注册功能
  7. 数据库导入Excel数据的简易方法
  8. JSF-受管Bean与EL表达式
  9. 基于Python的数据分析:数据库索引效率探究
  10. python笔记:#002#第一个python程序