[BZOJ2815]灾难

题目描述

阿米巴是小强的好朋友。

阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。

学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。

我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：

一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。

这个图没有环。

图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存；而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。

如果某个消费者的所有食物都灭绝了，它会跟着灭绝。

我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。

举个例子：在一个草场上，生物之间的关系是：

如

如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是1。但是，如果草突然灭绝，那么整个草原上的5种生物都无法幸免，所以，草的灾难值是4。

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

输入输出格式

输入格式：

输入文件 catas.in 的第一行是一个正整数 N，表示生物的种数。生物从 1 标

号到 N。

接下来 N 行，每行描述了一个生物可以吃的其他生物的列表，格式为用空

格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是 0 表示列

表的结束。

输出格式：

输出文件catas.out包含N行，每行一个整数，表示每个生物的灾难值。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

【样例说明】

样例输入描述了题目描述中举的例子。

【数据规模】

对50%的数据，N ≤ 10000。

对100%的数据，1 ≤ N ≤ 65534。

输入文件的大小不超过1M。保证输入的食物网没有环。

找的dp题然后和dp有啥关系???

思路挺好的一道题，也并不算很难

我们知道假如一个物种想死，那么他的所有食物都得死，否则他也死不了

而让他的食物都死，他的所有食物的LCA或LCA的父亲一定要死

这样我们就有思路了，先拓扑排序，按拓扑序将每个点挂在所有他食物的LCA下面

为什么要这么做呢?因为按拓扑序来处理到一个点的时候，他的所有食物一定已经被处理完了，这时才好统计他食物的LCA

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #define M 100010

 using namespace std;

 int n,num1,num2,num3;

 int head1[M],head2[M],head3[M],in[M],topo[M],deep[M],ans[M],fa[M][];

 struct point{int to,next;}e1[M<<],e2[M<<],e3[M<<];

 void add1(int from,int to) {e1[++num1].next=head1[from];e1[num1].to=to;head1[from]=num1;}

 void add2(int from,int to) {e2[++num2].next=head2[from];e2[num2].to=to;head2[from]=num2;}

 void add3(int from,int to) {e3[++num3].next=head3[from];e3[num3].to=to;head3[from]=num3;}

 void topsort()

 {

     queue<int>q;

     for(int i=;i<=n;i++)

         if(!in[i])

             q.push(i);

     int tot=;

     while(!q.empty())

     {

         int now=q.front(); q.pop();

         topo[++tot]=now;

         for(int i=head2[now];i;i=e2[i].next)

         {

             int to=e2[i].to;

             in[to]--;

             if(!in[to]) q.push(to);

         }

     }

 }

 int lca(int x,int y)

 {

     if(deep[x]<deep[y])swap(x,y);

     for(int i=;i>=;i--)

         if(deep[fa[x][i]]>=deep[y])

             x=fa[x][i];

     if(x==y)return y;

     for(int i=;i>=;i--)

         if(fa[x][i]!=fa[y][i])

             x=fa[x][i],y=fa[y][i];

     return fa[x][];

 }

 void dfs(int x)

 {

     for(int i=head3[x];i;i=e3[i].next)

     {

         int to=e3[i].to;

         dfs(to);

         ans[x]+=ans[to];

     }

     ans[x]++;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         while()

         {

             int x; scanf("%d",&x);

             if(!x) break;

             add1(i,x); add2(x,i); in[i]++;

         }

     }

     topsort();

     for(int i=;i<=n;i++)

     {

         int x=e1[head1[topo[i]]].to;

         for(int j=head1[topo[i]];j;j=e1[j].next) x=lca(x,e1[j].to);

         add3(x,topo[i]);

         deep[topo[i]]=deep[x]+;

         fa[topo[i]][]=x;

         for(int j=;j<=;j++) fa[topo[i]][j]=fa[fa[topo[i]][j-]][j-];

     }

     dfs();

     for(int i=;i<=n;i++) printf("%d\n",ans[i]-);

     return ;

 }

巴特西

[BZOJ2815]灾难

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章