原题解:
#include<bits/stdc++.h>
using namespace std;
int n,m,ru[5005],chu[5005],a,b,f[5005],ans;
int mp[5005][5005];
queue<int> q;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d", &a, &b);
mp[a][b]=1;//记录关系
chu[a]++;
ru[b]++;//记录入度和出度
}
for(int i=1;i<=n;i++){
if(ru[i]==0) {
f[i]=1;
q.push(i);//入度为零的入队
}
}
while(!q.empty()){//队列不为空
int a=q.front();
q.pop();//出队
for(int k=1;k<=n;k++){
if(mp[a][k]==0)continue;
f[k]+=f[a];//更新
f[k]%=80112002;
ru[k]--;//食物少了一个
if(ru[k]==0){//入队为零才入队
if(chu[k]==0){
ans+=f[k];
ans%=80112002;
continue;//有没有都行
}
q.push(k);
}
}
}
cout<<ans;
}
仿写:
#include <stdio.h>
int mg[5005][5005]={0}; //保存生物间吃与被吃的关系
int chu[5005]={0};//记录出度数
int ru[5005]={0};//入度
int f[5005]={0};//保存前一个结点到该结点的路径个数
int ans[5005]={0}; //记录是否为最佳消费者
int fr=-1,r=-1;
int qu[5005];
int main() {
int i,j,m,n,x,y,s,sum=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
mg[x][y] = 1;
}
for(i=1;i<=n;i++) //扫描数组mg,记录每个结点的出度与入度
for(j=1;j<=n;j++) {
if(mg[i][j]==1) {
chu[i]++;
ru[j]++;
}
}
for(i=1;i<=n;i++){
if(ru[i]==0)f[i]=1; //找出入度为0的最佳生产者
if(chu[i]==0)ans[i]=1; //记录最佳消费者
}
for(i=1;i<=n;i++) {
if(ru[i]==0) {
qu[++r]=i;
}
}
while(r!=fr){
fr++;
s=qu[fr];
for(i=1;i<=n;i++) {
if(mg[s][i]==1&&chu[s]!=0&&ru[s]==0) {
f[i]+=f[s];
chu[s]--;
ru[i]--;
if(ru[i]==0) //避免重复入队(即只有在入度为零时入队)
qu[++r]=i;
}
}
}
for(i=1;i<=n;i++) { //将最佳消费者的路径和相加,即最大食物链数
if(ans[i]==1){
sum=sum+f[i];
}
}
printf("%d",sum%80112002);
return 0;
}