menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[拓扑+DP]LOJ2060(HAOI2016)【食物链】题解
apps LOJ
local_offer 查看标签
comment 0 条评论

题目概述

给出 $n$ 个生物 $m$ 条能量流动,求食物链个数。

解题报告

脑子不好用了,划波水。生物题了解一下。

食物链的开始通常是绿色植物(生产者),从绿色植物开始至少要有三个营养级。书写食物链是从生态系统中能量传递起始的那种生物(生产者)开始,而不是非生物的成分,如太阳。食物链中有多种生物,后者可以取食前者,如在草原上,青草→野兔→狐狸→狼;在湖泊中,藻类→甲壳类→小鱼→大鱼。捕食食物链的第二个环节通常是植食性动物,第三个或其他环节的生物一般都是肉食性动物。

不同生物之间要用向右的箭头表示出物质和能量的流动方向。一条完整食物链的最后往往是相关叙述或者事实上的最高营养级,没有别的生物取食它。谚语“螳螂捕蝉,黄雀在后”可以书写出一条食物链:树→蝉→螳螂→黄雀。

——百度百科

反正就是说要从零入度点到零出度点,不能只有一个生物。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=200000;

int n,m,d[maxn+5],D[maxn+5],que[maxn+5];LL f[maxn+5],ans;
int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5];

#define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y),D[y]++,d[y]++;
    int Head=0,Tail=0;for (int i=1;i<=n;i++) if (!D[i]) que[++Tail]=i,f[i]=1;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x];j;j=nxt[j])
            {f[son[j]]+=f[x];if (!(--D[son[j]])) que[++Tail]=son[j];}
    for (int i=1;i<=n;i++) if (!lnk[i]&&d[i]) ans+=f[i];
    return printf("%lld\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up