洛谷：P4017：最大食物链计数

发布于 25th Apr 2025

题目

题目

分析

我们先分析样本数据。

这里有5种生物，7种捕食关系，如图：

flowchart TD 1-->2 1-->3 2-->3 3-->5 2-->5 4-->5 3-->4

1-->2表示1被2捕食。在这个表示方法中，箭头从被捕食者指向捕食者。

捕食和被捕食关系

我们这样来定义一个节点（“生物”——它既可以是别人的“食物”，也可以是捕猎别人的“猎手”）：

struct Organism
{
    int in_degree = 0;      // 入度：表示该生物可以捕食多少其他生物，有多少箭头指向该节点，也就是它食物来源的总数
    int out_degree = 0;     // 出度：表示该生物被多少其他生物捕食，有多少箭头从该节点出发，也就是它成为食物的总数
    vector<int> predators;  // 捕食者列表：列出能吃掉自己的生物
    vector<int> prey;       // 猎物列表：列出自己能吃掉的生物
};

其中：

in_degree和prey关联：表示该生物可以捕食多少其他生物
out_degree和predators关联：表示该生物被多少其他生物捕食

举例说明，对于生物1：

out_degree = 2，对应predators = {2, 3}：表示1被2和3捕食
in_degree = 0，对应prey = {}：表示1不捕食任何生物

显然，对于任何一个捕食关系来说，我们需要“成对”地更新这个关系对应的两个生物：

    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        organisms[a].predators.push_back(b);
        organisms[b].prey.push_back(a);
        organisms[a].out_degree++;
        organisms[b].in_degree++;
    }

从最根本的“来源”开始

这里和之前的题目P3916：图的遍历类似，都需要从“来源”开始遍历。

找到“纯粹”的食物来源（“生产者”，in_degree==0），它的DP表值一定是1——每个生产者都可以成为一条食物链的起点——进入队列等候处理。
```
for (int i = 1; i <= n; ++i)
{
    if (organisms[i].in_degree == 0)
    {
        dp[i] = 1;
        q.push(i);
    }
}
```
找到它的捕食者。捕食者的进食渠道（“食物链”）就是捕食者的来源的累积。同时，捕食者的进食渠道（in_degree）要减一。如果该捕食者的进食渠道为0，表明它用完了所有的进食渠道，只能成为别人的食物了，因此将其压入队列等候处理。

for (int v : organisms.predators)
{
  dp[v] = (dp[v] + dp) % MOD;
  if (--organisms[v].in_degree == 0)
  {
    q.push(v);
  }
}

食物链总数

最终，我们只要统计纯粹的“捕食者”（out_degree==0）各自有几条食物链能到达它，并加总即可。

    for (int i = 1; i <= n; ++i)
    {
        if (organisms[i].out_degree == 0)
        {
            result = (result + dp[i]) % MOD;
        }
    }

答案

Solution

思考

本题中，可以不维护in_degree和out_degree。这是因为：

入度和出度信息可以从predators和prey列表的长度得到：

// in_degree 等价于 prey.size()
// out_degree 等价于 predators.size()

在拓扑排序过程中：
- 判断是否为生产者：检查prey.empty()即可
- 判断是否为顶级消费者：检查predators.empty()即可
- 入度的减少可以通过从prey列表中移除元素来实现
算法复杂度分析：
- 时间复杂度：O(N + M)，其中N是生物数量，M是捕食关系数量
- 空间复杂度：O(N + M)，主要用于存储邻接表
- 使用列表长度替代degree计数不会影响复杂度
关键收获：
- 图的表示方法不是唯一的，可以根据实际需求选择合适的数据结构
- 有时看似必要的计数器实际可以用其他方式替代
- 拓扑排序非常适合处理具有层次关系的问题

Table of Contents

题目

分析

捕食和被捕食关系

从最根本的“来源”开始

答案

思考