P4017 最大食物链计数

发表于

P4017 最大食物链计数

题目背景

你知道食物链吗？Delia 生物考试的时候，数食物链条数的题目全都错了，因为她总是重复数了几条或漏掉了几条。于是她来就来求助你，然而你也不会啊！写一个程序来帮帮她吧。

题目描述

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。）

Delia 非常急，所以你只有 $1$ 秒的时间。

由于这个结果可能过大，你只需要输出总数模上 $80112002$ 的结果。

输入格式

第一行，两个正整数 $n$、$m$，表示生物种类 $n$ 和吃与被吃的关系数 $m$。

接下来 $m$ 行，每行两个正整数，表示被吃的生物 A 和吃 A 的生物 B。

输出格式

一行一个整数，为最大食物链数量模上 $80112002$ 的结果。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
5 7
1 2
1 3
2 3
3 5
2 5
4 5
3 4

输出 #1

1
5

说明/提示

各测试点满足以下约定：

测试点编号 $n$ $m$
$1,2$ $\le 40$ $\le 400$
$3,4$ $\le 100$ $\le 2\times 10^3$
$5,6$ $\le 10^3$ $\le 6\times 10^4$
$7,8$ $\le 2\times 10^3$ $\le 2\times 10^5$
$9,10$ $\le 5\times 10^3$ $\le 5\times 10^5$

对于 $100\%$ 的数据，$1 \le n \le 5\times 10^3,1\le m \le 5\times 10^5$

【补充说明】

数据中不会出现环，满足生物学的要求。（感谢 @AKEE）

思路分析 + 代码实现

本题是经典的拓扑排序例题，加上动态规划的思想。

什么是拓扑排序？

拓扑排序是对 有向无环图（DAG） 进行线性排序的方法，使得对于图中的每条有向边 $(u, v)$ ，节点 $u$ 在排序中都出现在节点 $v$ 之前。

为什么本题需要拓扑排序？

因为食物链是有方向的（A被B吃），且不能有环（生物学上食物链不能循环），这正好符合DAG的性质。我们需要按照食物链的方向计算路径数。

具体步骤

用 $indeg[i]$ 记录节点 $i$ 的入度， $cnt[i]$ 记录以节点 $i$ 结尾的食物链条数（取模后）

  1. 初始化队列： 将入度为零的点（生产者）加入队列（作为食物链的起点），并初始化 $cnt[i] = 1$

  2. BFS遍历：

  • 从队列中取出节点 $u$

  • 遍历 $u$ 的所有后继节点 $i$

  • 对每个后继节点 $v$：

    • 减少 $v$ 的入度（相当于删除边 $u \rightarrow i$）

    • 进行状态转移：$cnt[i] = (cnt[i] + cnt[u]) \mod MOD$

      • 状态转移方程 $cnt[i] = \sum cnt[u]$（其中 $u$ 是 $i$ 的前驱）

      • 意义：到达 $i$ 的路径数 = 所有到达 $u$ 的路径数之和（因为每条到 $u$ 的路径都可以延伸到 $i$）

    • 如果 $v$ 的入度变为 $0$ ，将 $v$ 加入队列

  • 重复直到队列为空

  1. 统计结果： 遍历所有节点，如果节点的出度为 $0$（即 $G[i].empty()$，顶级消费者），将 $cnt[i]$ 累加到答案中

本题中拓扑排序的作用

拓扑排序确保了计算顺序的正确性：

  • 只有在节点 $i$ 的所有前驱节点都被处理完后，$i$ 的入度才会变为0，$i$ 才会被加入队列

  • 这意味着当计算 $cnt[i]$ 时，所有到达 $i$ 的路径都已经被考虑到了

  • 从而保证了 $cnt[i] = \sum cnt[u]$ 的正确性

时间复杂度分析

  • 每个节点入队一次：$O(n)$

  • 每条边被访问一次：$O(m)$

  • 总时间复杂度：$O(n + m)$

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 5e3 + 5, MOD = 80112002;
vector<int> G[MAXN];
int indeg[MAXN], cnt[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, ans = 0;
    cin >> n >> m;
    for(int u, v, i = 0; i < m; i++) {
        cin >> u >> v;
        indeg[v]++;
        G[u].push_back(v);
    }
    queue<int> Q;
    for(int i = 1; i <= n; i++)
        if (indeg[i] == 0) {
            Q.push(i);
            cnt[i] = 1;
        }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(int i : G[u]) {
            indeg[i]--;
            cnt[i] = (cnt[i] + cnt[u]) % MOD;
            if (indeg[i] == 0) Q.push(i);
        }
    }
    for(int i = 1; i <= n; i++)
        if (G[i].empty()) 
            ans = (ans + cnt[i]) % MOD;
    cout << ans;
}

此外，还有利用 DFS + 记忆化搜索的方法，代码更简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 5e3 + 5, MOD = 80112002;
vector<int> G[MAXN];
int indeg[MAXN], cnt[MAXN];
int dfs(int u) {
    if (cnt[u]) return cnt[u]; // 已经计算过
    if (G[u].empty()) // 顶级消费者，只有自身一条链
        return cnt[u] = 1;
    int res = 0;
    for (int v : G[u]) // 累加所有后继的路径数
        res = (res + dfs(v)) % MOD;
    return cnt[u] = res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, ans = 0;
    cin >> n >> m;
    for(int u, v, i = 0; i < m; i++) {
        cin >> u >> v;
        indeg[v]++;
        G[u].push_back(v);
    }
    for(int i = 1; i <= n; i++)
        if (indeg[i] == 0)
            ans = (ans + dfs(i)) % MOD;
    cout << ans;
}