【BZOJ2815】【ZJOI2012】灾难 阿米巴和小强题 动态倍增LCA 灾难树

广告:

#include <stdio.h>
int main()
{
puts("转载请注明出处[vmurder]谢谢");
puts("网址:blog.csdn.net/vmurder/article/details/44104163");
}

题意:

原题面请见JSShining博客

http://www.cnblogs.com/JS-Shining/archive/2013/01/12/2857429.html

题解:

我们构建1颗灾害树,使得1个节点的任意1个先人灭绝,则其会灭绝。
则可以依照拓扑序扫每一个节点,然后加入到灾害树中时只需要把它的父亲赋成它所有食品的LCA就行了。
我们可以动态处理每一个节点的倍增lca数组fi,j表示i的第(1<<j)高先人。

代码:

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 70000
#define M 600000
#define LOGN 20
using namespace std;
struct KSD
{
int v,next;
}e[M],E[M],Ee[M];
int head[N],cnt,HEAD[N],CNT,Head[N];
inline void add(int u,int v)
{
e[++cnt].v=v;
Ee[cnt].v=u;
e[cnt].next=head[u];
Ee[cnt].next=Head[v];
Head[v]=head[u]=cnt;
}
inline void ADD(int u,int v)
{
E[++CNT].v=v;
E[CNT].next=HEAD[u];
HEAD[u]=CNT;
}
int f[N][LOGN],dep[N];
int getlca(int a,int b)
{
int i;
if(dep[a]<dep[b])swap(a,b);
for(i=LOGN-1;i>=0;i--)
if(dep[f[a][i]]>=dep[b])a=f[a][i];
if(a==b)return a;
for(i=LOGN-1;i>=0;i--)
if(f[a][i]!=f[b][i])
a=f[a][i],b=f[b][i];
return f[a][0];
}
int d[N],ans[N];
queue<int>q;
int dfs(int x)
{
ans[x]=1;
for(int i=HEAD[x];i;i=E[i].next)
ans[x]+=dfs(E[i].v);
return ans[x];
}
int n;
int main()
{
int i,j,k;
int a,b,c;
int u,v,lca;

scanf("%d",&n);
for(i=1;i<=n;i++)
{
while(scanf("%d",&a),a)
{
add(a,i);
d[i]++;
}
}
for(i=1;i<=n;i++)if(!d[i])add(n+1,i),d[i]=1;
q.push(n+1);
while(!q.empty())
{
u=q.front(),q.pop();
lca=0;
for(i=Head[u];i;i=Ee[i].next)
{
v=Ee[i].v;
if(i==Head[u])lca=v;
else lca=getlca(lca,v);
}
for(i=head[u];i;i=e[i].next)
{
d[v=e[i].v]--;
if(!d[v])q.push(v);
}
if(lca)
{
ADD(lca,u),f[u][0]=lca;
for(j=1;j<LOGN;j++)
f[u][j]=f[f[u][j-1]][j-1];
}
dep[u]=dep[lca]+1;
}
dfs(n+1);
for(i=1;i<=n;i++)printf("%d
"
,ans[i]-1);
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【BZOJ2815】【ZJOI2012】灾难 阿米巴和小强题 动态倍增LCA 灾难树

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡