洛谷 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;
}