题目链接: https://vjudge.net/contest/537778#problem/C

题意

给你 n 个动物，m 条他们之间吃与被吃的关系。

计算总共食物链的条数。(模上80112002)

(n <= 5e3, m <= 5e5)

思路

记录每一个动物的出边(被吃掉)和入边(可以吃掉)，然后沿着食物链方向，ret[i] = sum(ret[out[i]])，记忆化搜索下去。

这题还能用拓扑排序做。但是思路都大差不差。如果用拓扑就是正向的dp，一路先解决子问题再解决最终的问题。如果是记忆化搜索就是从最终的问题出发，向前要求得到每一个子问题的结果。

复杂度： O(m)

代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          putchar(10);
#define magic 80112002;

const int maxN = 5e3+10;
int dp[maxN];
std::vector<int> out[maxN], in[maxN];
int stk[maxN]; int c;

int down(int x) {
  if (!in[x].size()) { return 1; }
  if (dp[x]) { return dp[x]; }
  int me = 0;
  orep(i, 0u, in[x].size()) {
    me = (me + down(in[x][i])) % magic;
  }
  return dp[x] = me;
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  orep(i, 0, m) {
    int a, b; scanf("%d%d", &a, &b);
    out[a].push_back(b);
    in[b].push_back(a);
  }

  int ret = 0;
  orep(i, 1, n+1) {
    if (!out[i].size()) { ret = (ret + down(i)) % magic; }
  }
  printf("%d", ret);

  return 0;
}