这是我写的第5个正式题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 【A85523】最大食物链计数 题目链接 点这里 题目大意 有一张 nnn 个节点，mmm 条边的有向图（这里构造方式等会再说） 最终求最大食物链的节点数量 简单来讲，最大食物链就是 * 一张图中由多条边，多个节点构成的链 * 最左端节点出度为0，最右端节点入度为0 解题思路 1. 算法选择 拓扑排序+dp维护最小值 拓扑排序简单了解 * 选择拓扑排序是因为： 可以把这题看成 而要想得到“到兔子这一步时，最大食物链的节点数量”就必须要知道“到草这一步时，最大食物链节点的数量”，这不正是拓扑排序可以解决的吗？ * 选择dp是因为：我们需要动态求解到第i部分时，最大食物链的节点数量 2. 核心思路 1. 输入这张图并更新入度、出度值 > Q：输入什么图？关系是怎样的？ > A：输入有向图，关系：g[u].push_back(v) --> u节点被v节点吃 2. 拓扑排序 * 拓扑排序注意点: 3. 结算答案 对于每个食物链顶端（出度为0） 的节点，全部往最终答案中添加dp[i]的值 易错点/坑点 题目中说了，要对80112002取模 因此对于每步可能超出80112002的运算，都需要取模 AC 代码

#include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 80112002; const int N = 5010; int n, m; vector<int> g[N]; int in_deg[N], out_deg[N]; int dp[N]; void topo_sort() { queue<int> q; for (int i = 1; i <= n; i++) { if (in_deg[i] == 0) { dp[i] = 1; q.push(i); } } while (!q.empty()) { int f = q.front(); q.pop(); for (int i = 0;i < g[f].size();i++){ int now = g[f][i]; dp[now] = (dp[f] + dp[now]) % MOD; in_deg[now]--; if (in_deg[now] == 0){ q.push(now); } } } } signed main() { }