[HAOI2016] 食物链

题意

给一个有向无环图，边表示能量从一个物种流向另一个物种。

一条合法食物链应当：

从一个入度为 0 的点开始
沿有向边一直走
结束在一个出度为 0 的点

题目要求这样的路径总条数。孤立点不算一条食物链。

思路

先看一个可以直接验证想法的朴素解：

cpp

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, m;
vector<int> g[MAXN];
int indeg[MAXN], outdeg[MAXN];

int dfs(int u) {
    if (outdeg[u] == 0) {
        return 1;
    }

    int ret = 0;
    for (int i = 0; i < (int) g[u].size(); i++) {
        int v = g[u][i];
        ret += dfs(v);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        indeg[v]++;
        outdeg[u]++;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0 && outdeg[i] > 0) {
            ans += dfs(i);
        }
    }

    cout << ans << '\n';
    return 0;
}

如果数据很小，我们可以从每个入度为 0 的点出发，DFS 枚举所有走到出度为 0 的路径。

但这会重复枚举大量公共后缀，数据一大就不行了。

题目保证这个图符合生物学特点，本质上就是一个 DAG。

因此可以按拓扑序做路径计数。

设：

dp[i] 表示从任意一个合法起点走到点 i 的路径条数

那么：

所有入度为 0 的点都可以作为起点，所以先令 dp[i] = 1
按拓扑序遍历每个点 u
对每条边 u -> v，把 dp[u] 累加到 dp[v]

最后：

所有出度为 0 的点都是合法终点
把这些点的 dp 值加起来，就是答案

孤立点不会出错，因为它虽然入度为 0``，但同时出度也为 0`，题意说它不算食物链；而我们的转移里，只有真正形成路径的点才会对答案有贡献。更准确地说，只有从某个起点沿边走到终点的情况才会被统计。对于孤立点，它不会通过任何边形成链条。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXM = 200005;

int n, m;
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
int indeg[MAXN], outdeg[MAXN];
int dp[MAXN]; // dp[i] 表示从任意起点走到 i 的食物链条数。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        indeg[v]++;
        outdeg[u]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            q.push(i);
            // 只有不是孤立点的源点，才能作为一条食物链的起点。
            if (outdeg[i] > 0) {
                dp[i] = 1;
            }
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            dp[v] += dp[u];
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        // 只有真正形成路径的汇点才计入答案，孤立点的 dp 仍然是 0。
        if (outdeg[i] == 0) {
            ans += dp[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

拓扑排序和一次路径计数都只会遍历每个点、每条边一次。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。

总结

这题的关键在于把“食物链条数”翻译成：

DAG 上从所有源点出发
到所有汇点结束
的路径总数

一旦看出这是 DAG 路径计数，拓扑排序上的 DP 就是标准做法。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

代码

复杂度

总结

一图流解析