洛谷 P4017 最大食物链计数

洛谷传送门

题目背景

你知道食物链吗?Delia生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。

题目描述

给你一个食物网,你要求出这个食物网中最大食物链的数量。

(这里的“最大食物链”,指的是生物学意义上的食物链,即最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者。)

Delia非常急,所以你只有1秒的时间。

由于这个结果可能过大,你只需要输出总数模上80112002的结果。

输入格式

第一行,两个正整数n、m,表示生物种类n和吃与被吃的关系数m。

接下来m行,每行两个正整数,表示被吃的生物A和吃A的生物B。

输出格式

一行一个整数,为最大食物链数量模上80112002的结果。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

各测试点满足以下约定:

【补充说明】

数据中不会出现环,满足生物学的要求。(感谢@AKEE )

题解:

一道拓扑排序的好题。

前置知识是拓扑排序。如有不会的小伙伴请移步:

拓扑排序详解

我个人认为拓扑排序本身并没有特别难以理解,但是应用在题目上却并不是那么容易。

首先我们发现这道题是一道图论题。(这个要是看不出来可真的GG了)

对于图论题,我们要好好分析题目大意,据此判断模板和算法。那么这道题为什么要用拓扑排序呢

首先,我们要找最大食物链,最大食物链是什么呢?根据题目的描述,是最猛的那种生物不能被任何生物吃掉,最弱的生物不能吃任何生物。类比到图上,就是从一个入度为0的点,到一个出度为0的点。我们只需要找出所有这种数量即可。

用递推即可解决计数的问题:

#include<cstdio>
#include<queue>
using namespace std;
const int maxn=5010;
const int maxm=5*1e5+10;
const int mod=80112002;
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
    int x=0,f=1;
    char ch=nc();
    while(ch<48){if(ch=='-')f=-1;ch=nc();}
    while(ch>47)    x=(((x<<2)+x)<<1)+ch-48,ch=nc();
    return x*f;
}
int n,m;
int tot,head[maxn],nxt[maxm],to[maxm];
int chudu[maxn],rudu[maxn];
int f[maxn],ans;
queue<int> q;
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int a=read();
        int b=read();
        add(a,b);
        rudu[b]++;
        chudu[a]++;
    }
    for(int i=1;i<=n;i++)
        if(rudu[i]==0)
            f[i]=1,q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            f[y]=(f[y]+f[x])%mod;
            rudu[y]--;
            if(rudu[y]==0)
            {
                q.push(y);
                if(chudu[y]==0)
                    ans=(ans+f[y])%mod;
            }
        }
    }
    printf("%d",ans);
    return 0;
}
01-06 17:50