这是我写的第5个正式题解

---

【A85523】最大食物链计数

题目链接

点这里

题目大意

有一张 $n$ 个节点，$m$ 条边的有向图（这里构造方式等会再说）
最终求最大食物链的节点数量
简单来讲，最大食物链就是

• 一张图中由多条边，多个节点构成的链
• 最左端节点出度为0，最右端节点入度为0

解题思路

1. 算法选择

拓扑排序+dp维护最小值
拓扑排序简单了解

• 选择拓扑排序是因为：
  可以把这题看成

鹰 --> 兔子 --> 草

而要想得到“到兔子这一步时，最大食物链的节点数量”就必须要知道“到草这一步时，最大食物链节点的数量”，这不正是拓扑排序可以解决的吗？

• 选择dp是因为：我们需要动态求解到第i部分时，最大食物链的节点数量

2. 核心思路

1. 输入这张图并更新入度、出度值

Q：输入什么图？关系是怎样的？
A：输入有向图，关系：g[u].push_back(v) --> u节点被v节点吃

2. 拓扑排序

• 拓扑排序注意点:

for (int i = 0;i < g[f].size();i++){
    int now = g[f][i];
    dp[now] = (dp[f] + dp[now]) % MOD;
    // 注意是更新dp[now]（上级），这里的关系容易搞混
    in_deg[now]--;
    if (in_deg[now] == 0){
        q.push(now);
    }
}

3. 结算答案
   对于每个食物链顶端（出度为0） 的节点，全部往最终答案中添加dp[i]的值

易错点/坑点

题目中说了，要对20021108取模

因此对于每步可能超出20021108的运算，都需要取模

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() {
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        out_deg[u]++;
        in_deg[v]++;
    }
    topo_sort();
    int ans = 0;
    for (int i = 1;i <= n;i++){
        if (out_deg[i] == 0){
            ans = (ans + dp[i]) % MOD;
        }
    }
    cout << ans;
    
    return 0;
}