洛谷P4017《最大食物链计数》

二月 04, 2019 2874

七年级上册生物题目

题目背景

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

题目描述

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

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

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

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

输入输出格式

输入格式

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

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

输出格式

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

输入输出样例

输入样例#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

说明

各测试点满足以下约定：

图源洛谷

【补充说明】

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

解题思路

有向无环？拓扑序啊！
仔细想一下发现思路可能是对的

正向建一个图，反向建一个图

先把正向图的拓扑序跑出来，放到一个vector<int>里
再按照拓扑序来枚举点，这样就保证了枚举的顺序

我们设 dp[node] 表示以编号 node 为结尾的食物链个数
那么对于节点 Node，

  • 如果它没有出边，那么dp[node] = 1
  • 如果它有出边，那么枚举每一条出边的邻接点nv，dp[node] += dp[nv]

最后答案是 \sum dp[所有没有出边的点]

代码实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)
#define ADD(__x) if (__x >= HA) __x -= HA
#define DEBUG(__Args,...) printf(__Args,##__VA_ARGS__)

using std::cin;
using std::cout;
using std::endl;
using std::max;

const int MAXN = 5000 + 10;
const int HA = 80112002;

std::vector<int> head[MAXN];
std::vector<int> reallink[MAXN];
std::vector<int> top;

int id[MAXN]; // id -> in degree
int n, m, ans; 

int dp[MAXN]; 
// dp[i][j] -> the amount of links that the end-node = i

void Topsort() {
    std::queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!id[i]) {
            q.push(i);
            top.push_back(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int amt = head[u].size();
        for (int i = 0; i < amt; ++i) {
            int v = head[u][i];
            --id[v];
            if (!id[v]) {
                top.push_back(v);
                q.push(v);
            }
        }
    }
}

int main() {
    IMPROVE_IO();
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
    	int A = 0, B = 0;
    	cin >> A >> B;
    	head[A].push_back(B);
    	reallink[B].push_back(A);
    	++id[B];
    }
    Topsort();
    for (int i = 1; i <= n; ++i) {
        // enumerate Topsorted-Nodes
        int nnode = top[i - 1];
        if (reallink[nnode].size() == 0) dp[nnode] = 1;
        // no out-edges connected
        for (int j = 0; j < reallink[nnode].size(); ++j) {
            int nenode = reallink[nnode][j];
            dp[nnode] += dp[nenode];
            ADD(dp[nnode]);
        }
        if (!head[nnode].size()) ans += dp[nnode];
        ADD(ans);
    }
    cout << ans << endl;
    return 0;
}