首页 > 代码库 > [日常训练]大灾难
[日常训练]大灾难
Description
在一个生态圈中,食物链的维系是很重要的。食物链的断裂往往引起连锁反应,进而招致生态系统如同多米诺骨牌一样坍塌。
现在考虑一个简化模型。在一个生态系统中,有$N$种生物,它们分为两类:生产者与消费者。生产者通过这个系统之外的能量来生存,最常见的是植物的光合作用。而消费者需要“消费”,也就是以其他生物为食物才可以生存。为了简化问题,我们假设所有消费者是可以分层的,高一层的消费者可能的食物来源都来自它的严格下层。生产者可以视为最下层的成员。当一种生物灭绝之后,依赖于它的消费者会由于所有食物消失而灭绝。 而这些消费者的灭绝可能进一步引起它的上层成员灭绝。我们定义指标$C(x)$,用于表示当x从生态系统中消失之后,随它灭绝的生物数量。
给定一个食物链模型,对所有生物,计算它的灭绝指标$C(x)$。
Input
第一行一个整数$N,表示生物的数量。生物从$1$开始编号。
接下来$N$行,第$i$行表示第$i$种生物的食物列表。两种食物的编号以空格隔开,输入$0$表示本行结束。如果这一行只有一个$0$,这是一个生产者,不能认为它没有食物而天然灭绝。
Output
共$N$行,第$i$行是第$i$个生物的灭绝指标$C(i)$。
Sample Input
501 01 02 3 02 0Sample Output
4 1 0 0 0HINT
$N\;\leq\;65534$，输入保证合法(即可以分层)。输入文件大小不超过$1MB$。
Solution
显然,整张食物网是$DAG$.
利用$topo$序将图分层.
一个物种会灭亡当且仅当它的所有食物的公共祖先灭亡.
建树,每个物种的所有食物的公共祖先向每个物种连一条边,求子树大小.
#include<cmath>#include<ctime>#include<queue>#include<stack>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define K 17#define N 65535#define M 300000using namespace std;struct graph{ int nxt,to;}e[N<<1],e1[M],e2[M];struct lives{ int n,dep;}a[N];int f[N][K],t[N],g[N],g1[N],g2[N],dep[N],siz[N],n,cnt,tot;queue<int> q;inline void adde1(int x,int y){ e1[++cnt].nxt=g1[x];g1[x]=cnt;e1[cnt].to=y;}inline void adde2(int x,int y){ e2[++tot].nxt=g2[x];g2[x]=tot;e2[tot].to=y;}inline void addedge(int x,int y){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;}inline bool cmp(lives x,lives y){ return x.dep<y.dep;}inline void toposort(){ int u; for(int i=1;i<=n;++i) if(!t[i]) q.push(i); while(!q.empty()){ u=q.front();q.pop();a[u].dep=++tot; for(int i=g1[u];i;i=e1[i].nxt) if(!(--t[e1[i].to])) q.push(e1[i].to); }}inline void dfs(int u){ siz[u]=1; for(int i=g[u];i;i=e[i].nxt){ dfs(e[i].to);siz[u]+=siz[e[i].to]; }}inline int swim(int x,int h){ for(int i=0;h;++i,h>>=1) if(h&1) x=f[x][i]; return x;}inline int lca(int x,int y){ int i,t; if(dep[x]<dep[y]){ t=x;x=y;y=t; } x=swim(x,dep[x]-dep[y]); if(x==y) return x; while(true){ for(i=0;f[x][i]!=f[y][i];++i); if(!i) return f[x][0]; x=f[x][i-1];y=f[y][i-1]; }}inline void Aireen(){ scanf("%d",&n); for(int i=1,k;i<=n;++i){ while(true){ scanf("%d",&k); if(!k) break; adde1(k,i);++t[i];adde2(i,k); } } tot=cnt=0;toposort(); for(int i=1;i<=n;++i) a[i].n=i; sort(a+1,a+1+n,cmp); for(int q=1,i,j,l;q<=n;++q){ i=a[q].n;j=g2[i]; if(j){ l=e2[j].to; for(j=e2[j].nxt;j;j=e2[j].nxt) l=lca(e2[j].to,l); addedge(l,i); f[i][0]=l; for(int k=1;k<K;++k) f[i][k]=f[f[i][k-1]][k-1]; dep[i]=dep[l]+1; } else{ addedge(0,i); for(int k=0;k<K;++k) f[i][k]=0; dep[i]=1; } } dfs(0); for(int i=1;i<=n;++i) printf("%d\n",siz[i]-1);}int main(){ freopen("catas.in","r",stdin); freopen("catas.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0;}
[日常训练]大灾难
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。