P4017 最大食物链计数题目背景你知道食物链吗Delia 生物考试的时候数食物链条数的题目全都错了因为她总是重复数了几条或漏掉了几条。于是她来就来求助你然而你也不会啊写一个程序来帮帮她吧。题目描述给你一个食物网你要求出这个食物网中最大食物链的数量。这里的“最大食物链”指的是生物学意义上的食物链即最左端是不会捕食其他生物的生产者最右端是不会被其他生物捕食的消费者。Delia 非常急所以你只有1 11秒的时间。由于这个结果可能过大你只需要输出总数模上80112002 8011200280112002的结果。输入格式第一行两个正整数n nn、m mm表示生物种类n nn和吃与被吃的关系数m mm。接下来m mm行每行两个正整数表示被吃的生物 A 和吃 A 的生物 B。输出格式一行一个整数为最大食物链数量模上80112002 8011200280112002的结果。输入输出样例 #1输入 #15 7 1 2 1 3 2 3 3 5 2 5 4 5 3 4输出 #15说明/提示各测试点满足以下约定测试点编号n nnm mm1 , 2 1,21,2≤ 40 \le 40≤40≤ 400 \le 400≤4003 , 4 3,43,4≤ 100 \le 100≤100≤ 2 × 10 3 \le 2\times 10^3≤2×1035 , 6 5,65,6≤ 10 3 \le 10^3≤103≤ 6 × 10 4 \le 6\times 10^4≤6×1047 , 8 7,87,8≤ 2 × 10 3 \le 2\times 10^3≤2×103≤ 2 × 10 5 \le 2\times 10^5≤2×1059 , 10 9,109,10≤ 5 × 10 3 \le 5\times 10^3≤5×103≤ 5 × 10 5 \le 5\times 10^5≤5×105对于100 % 100\%100%的数据1 ≤ n ≤ 5 × 10 3 , 1 ≤ m ≤ 5 × 10 5 1 \le n \le 5\times 10^3,1\le m \le 5\times 10^51≤n≤5×103,1≤m≤5×105【补充说明】数据中不会出现环满足生物学的要求。感谢 AKEE解析/* 入度为0到出度为0的结点的路径数, 起初每一个入度为0的结点都可以贡献一条新路径 可以想象成每一个入度为0的结点都可以贡献能量, 然后该结点出度所对应的结点可以 吸收之前结点传递而来的能量 */#includeiostream#includevector#includequeueusingnamespacestd;constexprintMOD80112002;structEdge{inttoNode,nextEdge;};intn,m,x,y;vectorinthead;vectorEdgeedges;intcnt;vectorintisDel;// 记录该结点是否被删除vectorintenergy;// 记录结点可贡献能量vectorintindegree,outdegree;// 入度, 出度intans;voidaddEdge(intu,intv){edges[cnt]{v,head[u]};head[u]cnt;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinnm;head.resize(n1,-1);edges.resize(m);energy.resize(n1);indegree.resize(n1);outdegree.resize(n1);for(inti0;im;i){cinxy;addEdge(x,y);outdegree[x];indegree[y];}// topo序列遍历queueintq;for(inti1;in;i){if(indegree[i]0){energy[i]1;q.push(i);}}inte;while(!q.empty()){eq.front(),q.pop();for(intihead[e];i!-1;iedges[i].nextEdge){inttoNodeedges[i].toNode;energy[toNode](energy[toNode]energy[e])%MOD;// 防溢出if(--indegree[toNode]0)q.push(toNode);}}// 最后统计所有出度为0结点的能量和就行for(inti1;in;i){if(outdegree[i]0){ans(ansenergy[i])%MOD;}}coutans;return0;}