JCYZOJ3 食物链

题目描述

在大自然中,对于两种生物X 和Y,如果X 可以被Y 吃,
那么连一条X 到Y 的有向边,那么我们就得到了一个食物网。
有些生物不会吃别人,我们称这类生物为A,有些生物不会被
别人吃,我们称这类生物为B,而食物链就是从A 到B 的任意
一条路径。现在给出你n 种生物以及m 条X 可以被Y 吃的关系,
(意思是这n 种生物之间只存在这m 条关系)请你输出食物链
的条数mod 23333333 的结果。

输入格式

第一行输入n 和m。
接下来m 行每行两个数x,y,表示x 被y 吃。

输出格式

输出一行表示输出食物链的条数mod 23333333 的结果。

样例输入

4 4
1 2
2 4
1 3
3 4

样例输出

2
输入文件A.in
输出文件A.out

数据范围

对于40%的数据,满足n,m<=10
对于100%的数据,满足n,m<=100000

拓扑排序+DP

#include<cstdio>
#include<queue>
using namespace std;
int n,m,rd[100010],f[100010],tot,t[100010],he[100010],next[100010],ans;
bool ins[100010],outs[100010];
queue<int> head;
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		rd[x]++;
		ins[x]=1;
		outs[y]=1;
		t[++tot]=x;next[tot]=he[y];he[y]=tot;
	}
	for(int i=1;i<=n;i++)
		if(rd[i]==0){head.push(i); f[i]=1;}
	while(!head.empty()){
		int q=head.front();head.pop();
		for(int x=he[q],i=t[x];i!=0&&x!=0;x=next[x],i=t[x]){
			f[i]=(f[i]+f[q])%23333333;
			rd[i]--;
			if(rd[i]==0)head.push(i);
			}
	} 
	for(int i=1;i<=n;i++)if(ins[i]&&!outs[i])ans=(ans+f[i])%23333333;
	printf("%d",ans);
}

 

此条目发表在DP, JCYZOJ, 拓扑排序, 排列组合分类目录。将固定链接加入收藏夹。