最大食物链计数

GitHub跳转原题关系图返回列表

从所有入度为零的生产者开始拓扑 DP，把路径条数沿捕食边累加到出度为零的消费者。

OJ: luogu

题目 ID: P4017

难度:普及/提高-

标签:DAG拓扑排序动态规划计数python

日期: 2026-07-16 18:42

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

在无环食物网中，边 A -> B 表示 B 吃 A。统计从不捕食其他生物的生产者到不被其他生物捕食的消费者的路径数量，答案模 80112002。

思路

生产者是入度为 0 的点，消费者是出度为 0 的点。令 ways[v] 表示从任意生产者走到 v 的食物链条数：

  • 每个生产者初始化 ways=1；
  • 拓扑处理中遇到边 u -> v，执行 ways[v]+=ways[u]；
  • 最后把所有消费者的 ways 相加。

样例的状态变化如下，表中“新增来源”说明本轮由哪条边贡献：

处理点 新增来源 处理后的关键状态
1 生产者初值 ways[2]=1, ways[3]=1
2 1 -> 2 ways[3]=2, ways[5]=1
3 两条到 3 的路径 ways[4]=2, ways[5]=3
4 两条到 4 的路径 ways[5]=5

唯一消费者 5 最终得到 5 条链。

Python 知识

  • deque 支持 O(1)O(1) 的 popleft，适合 Kahn 拓扑队列。
  • deque(node for ... if ...) 用生成器直接初始化所有零入度点。
  • sum(ways[node] for ... if not graph[node]) 只汇总出度为零的消费者。
  • 每次转移立即取模，防止路径数大幅增长。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：deque 队列。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：条件生成器与 sum。

代码

python
import sys
from collections import deque


MOD = 80112002


def main():
    read = sys.stdin.buffer.readline
    n, m = map(int, read().split())
    graph = [[] for _ in range(n + 1)]
    indegree = [0] * (n + 1)

    for _ in range(m):
        prey, predator = map(int, read().split())
        graph[prey].append(predator)
        indegree[predator] += 1

    queue = deque(node for node in range(1, n + 1) if indegree[node] == 0)
    ways = [0] * (n + 1)
    for source in queue:
        ways[source] = 1

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            ways[neighbor] = (ways[neighbor] + ways[node]) % MOD
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    print(sum(ways[node] for node in range(1, n + 1) if not graph[node]) % MOD)


if __name__ == "__main__":
    main()
cpp
/**
 * P4017 最大食物链计数
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
const int MAXM = 500005;
const int MOD = 80112002;

int head[MAXN], to[MAXM], nxt[MAXM], cnt;
int indeg[MAXN], outdeg[MAXN];
int ways[MAXN]; // 到达该结点的食物链数
int n, m;

void add_edge(int u, int v) {
    ++cnt;
    to[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add_edge(a, b);
        ++indeg[b];
        ++outdeg[a];
    }
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (indeg[i] == 0) {
            q.push(i);
            ways[i] = 1; // 生产者：食物链数为 1
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            ways[v] = (ways[v] + ways[u]) % MOD;
            --indeg[v];
            if (indeg[v] == 0) q.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        if (outdeg[i] == 0) // 顶级消费者
            ans = (ans + ways[i]) % MOD;
    printf("%d\n", ans);
    return 0;
}

复杂度

每个点和每条边处理一次，时间复杂度 O(n+m)O(n+m)，空间复杂度 O(n+m)O(n+m)。

总结

DAG 路径计数的核心是让拓扑序保证“前驱贡献全部到齐后再处理当前点”。起点初始化为一，沿边累加，终点汇总即可。