P4017 最大食物链计数
解题思路
这题就是拓扑排序
拓扑排序的精髓就在于每个点只会入队一次,每条边只会通过一次,所以时间复杂度就有很好的保证,O(N+M),SPFA的玄学时间复杂度)。
正确性说明:题目的补充说明告诉我们这是一张DAG(有向无环图),因此必定存在一个入度为0的点,也因此每一个点都会被遍历。
下面的代码的变量解释:
fi 表示到达 i 时的路径数;
hi 表示在可以直接吃掉 i 的所有关系中最后的一条的编号(邻接矩阵用);
rudu 表示 i 的入度,是整个程序的核心数组;
chdu 表示 i 的出度;
结构体 a 记录 m 条关系。
当一个点的入度变为零,即所有它能吃的东西都已经搜索过了,这是它的数值就不会发生变化,就可以入队了。这样保证了队列里的所有数值都不会发生变化。
AC代码
#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,s,h,t,tot,c[10005],p[10005],f[10005],rudu[10005],chudu[10005],head[10005];
struct node
{
long long to,next;
}a[500005];
void add(int x,int y)//邻接表
{
a[++tot]=(node){
y,head[x]};
head[x]=tot;
}
void tp()//拓扑排序
{
for(int i=1;i<=n;i++)//进队
if(rudu[i]==0){
p[++t]=i;f[i]=1;}
while(h<t)
{
h++;
for(int i=head[p[h]];i;i=a[i].next)
{
f[a[i].to]+=f[p[h]];
f[a[i].to]=f[a[i].to]%80112002;
rudu[a[i].to]--;
if(rudu[a[i].to]==0)
{
if(chudu[a[i].to]==0) //为最低级
{
s+=f[a[i].to];
f[a[i].to]=f[a[i].to]%80112002;
}
else p[++t]=a[i].to;//进队
}
}
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
long long x,y;
scanf("%lld%lld",&x,&y);
add(x,y);
chudu[x]++;//出度入度都+1
rudu[y]++;
}
tp();
cout<<s%80112002;
}