洛谷 P4017 最大食物链计数

题目传送门

解题思路:

一个DAG上的DP,先拓扑排序,再跑dp,f[i]表示到i有多少条食物链.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<queue>
 5 
 6 using namespace std;
 7 
 8 int n,m,_in[5001],f[5001],_out[5001],ans;
 9 vector<int> a[5001];
10 bool vis[5001];
11 queue<int> q;
12 
13 inline void solve(int fa) {
14     q.push(fa);
15     f[fa] = 1;
16     while(!q.empty()) {
17         int u = q.front();
18         q.pop();
19         for(int i = 0;i < a[u].size(); i++) {
20             f[a[u][i]] = (f[a[u][i]] + f[u]) % 80112002;
21             _in[a[u][i]]--;
22             if(_in[a[u][i]] == 0)
23                 q.push(a[u][i]);
24         }
25     }
26 }
27 
28 int main() {
29     scanf("%d%d",&n,&m);
30     for(int i = 1;i <= m; i++) {
31         int x,y;
32         scanf("%d%d",&x,&y);
33         _in[y]++;_out[x]++;
34         a[x].push_back(y);
35         vis[y] = 1;
36     }
37     for(int i = 1;i <= n; i++) 
38         if(!vis[i])
39             solve(i);
40     for(int i = 1;i <= n; i++) 
41         if(_out[i] == 0)
42             ans += f[i];
43     printf("%d",ans % 80112002);
44     return 0;
45 }