申请会员ID： SiJin233【申请通过】
1. 申 请 I D：SiJin2332. 个人邮箱：lhz1274590021@vip.qq.com
3. 原创技术文章：
# 洛谷P4017 最大食物链计数 解决方案
# 题目重现
Delia给了你一个食物网，要你求出这个食物网中最大食物链的数量。
（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）
Delia 非常急，所以你只有 1 秒的时间
由于这个结果可能过大，你只需要输出总数模上 80112002 的结果
## 输入：
第一行，两个正整数 n、m，表示生物种类 n 和 吃与被吃的关系数 m（n<=5000，m<=500000）
接下来 m 行，每行两个正整数，表示被吃的生物A 和 吃A的生物B
## 输出：
一行一个整数，为最大食物链数量模上 80112002 的结果。
## 样例：
> 输入样例#1
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4
输出样例#1
5
# 解题思路
> 在开始分析之前，先复习一遍拓扑排序的知识，掌握拓扑排序才能理解并完成此题
我们不妨先根据测试样例画出一张图来方便分析
可以发现：食物网本质上是一张有向无环的AOV-网
食物网中的生物 —— **顶点**
生物之间的关系 —— **有向边**
> 最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者
根据题意得出，最左端的生产者入度为0，最右端的消费者出度为0
所以求** 最大食物链的数量** 可以转换为求** 所有拓扑序列的数量** 也就是求 **入度为0** 且 **出度为0** **路径的数量**
再次分析能够发现，如蓝色箭头所示：
+ 5 号点，出度为0，全部路径数量取决于：到 5 号点的三个点（ 2 号、3 号、4 号）的食物链条数的总和
+4 号点的全部路径数量取决于：到 4 号点的一个点（ 3 号）的食物链条数
+ 3 号点的全部路径数量取决于：到 3 号点的两个点（ 1 号、2 号）的食物链条数的总和
+ 2 号点的全部路径数量取决于：到 2 号点的一个点（ 1 号）的食物链条数
+ 1 号点，因入度为0，所以全部路径数量为1
得出结论：对于任一顶点的路径数量，都取决于**和它连接的所有前一顶点**的路径数量的总和
因此，我们得到了**算法的核心思路**：
在**拓扑排序**时，声明一个存放所有顶点路径数量的数组，在删除入度为0的顶点时，将 删除的顶点 的路径数量 加到 和它连接的所有后一顶点的路径数量上
最后，输出所有出度为 0 的顶点的路径数量总和 即为正确答案
# 代码模拟
为加深对 拓扑排序 及 本题核心思路 的理解，让我们来模拟一次操作测试数据的全部过程
+ 第一步：初始化 顶点路径数量数组，将入度为0的 1 号点 加入队列
+ 第二步：删除 1 号点，将 1 号点的路径数量 加到 和它连接的 2 号点和 3 号点的路径数量上，将入度为0的 2 号点 加入队列
+ 第三步：删除 2 号点，将 2 号点的路径数量 加到 和它连接的 3 号点和 5 号点的路径数量上，将入度为0的 3 号点 加入队列
+ 第四步：删除 3 号点，将 3 号点的路径数量 加到 和它连接的 4 号点和 5 号点的路径数量上，将入度为0的 4 号点 加入队列
+ 第五步：删除 4 号点，将 4 号点的路径数量 加到 和它连接的 5 号点的路径数量上，将入度为0的 5 号点 加入队列
+ 第六步： 5 号点出度为0，且全部顶点遍历完成，输出最大食物链条数的数量 5
由此，我们可以在**拓扑排序**算法的基础上增加 记录路径数量 功能，从而写出全部代码
```cpp
#include <iostream>
#include<queue>
using namespace std;
#define MOD 80112002
int n, m;//n:生物种类 m:吃与被吃的关系总数
int relation;//吃与被吃的关系
int in, out;//记录每个顶点的入度和出度
queue<int> Q;//拓扑排序队列
int amount;//记录每个顶点的食物链条数
int i;
int result;//结果
void Process() {
//寻找入度为0的点进入队列
for (i = 1; i <= n; i++) {
if (in == 0) {
Q.push(i);
amount = 1;
}
}
//当队列不为空时持续处理
int cur;
while (!Q.empty()) {
cur = Q.front();
Q.pop();
for (i = 1; i <= n; i++) {
if (relation == 1) {
in--;
amount += amount;
amount %= MOD;
if (in == 0) {
if (out == 0) {
result += amount;//可能存在多个最右端出度为0的消费者
result %= MOD;
continue;
}
Q.push(i);
}
}
}
}
}
int main() {
cin >> n >> m;
int tempA, tempB;
//读入数据
for (i = 1; i <= m; i++) {
cin >> tempA >> tempB;
relation = 1;
in++;
out++;
}
//处理数据
Process();
//输出结果
cout << result;
return 0;
}
``` I D：SiJin233
邮箱：lhz1274590021@vip.qq.com
申请通过，欢迎光临吾爱破解论坛，期待吾爱破解有你更加精彩，ID和密码自己通过邮件密码找回功能修改，请即时登陆并修改密码！
登陆后请在一周内在此帖报道，否则将删除ID信息。 Hmily 发表于 2023-9-12 15:23
I D：SiJin233
邮箱：
来报道啦！感谢哥的审核和机会{:17_1074:}
页:
[1]