bzoj4562: [Haoi2016]食物链--记忆化搜索

这道题其实比较水，半个小时AC= =对于我这样的渣渣来说真是极大的鼓舞

题目大意：给出一个有向图，求入度为0的点到出度为0的点一共有多少条路

从入读为零的点进行记忆化搜索，搜到出度为零的点返回1

所有返回值加起来就是答案。

“注意单独的一种孤立生物不算一条食物链。”出题人都这么好心的说了，然而第一次交的时候还是忘了= =结果成为此题第一个WA的人hh

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define maxn 100010
 5 using namespace std;
 6 struct node{
 7     int from,to,next;
 8 }e[maxn*2];
 9 int head[maxn],vis[maxn],dp[maxn],ind[maxn],out[maxn];
10 int tot,n,m,u,v;
11 
12 void insert(int u, int v){
13     e[++tot].from=u;
14     e[tot].to=v;
15     e[tot].next=head[u];
16     head[u]=tot;
17 }
18 
19 int dfs(int x){
20     if (vis[x]) return dp[x];
21     vis[x]=1;
22     if (out[x]==0){
23         dp[x]=1;
24         return 1;
25     }
26     int sum=0;
27     for (int i=head[x]; i!=-1; i=e[i].next){
28         int v=e[i].to;
29         sum+=dfs(v);
30     }
31     dp[x]=sum;
32     return sum;
33 }
34 
35 int main(){
36     scanf("%d%d", &n, &m);
37     memset(ind,0,sizeof(ind));
38     memset(out,0,sizeof(out));
39     memset(head,-1,sizeof(head));
40     tot=-1;
41     for (int i=1; i<=m; i++){
42         scanf("%d%d", &u, &v);
43         out[u]++;
44         ind[v]++;
45         insert(u,v);
46     }
47     int ans=0;
48     memset(vis,0,sizeof(vis));
49     memset(dp,0,sizeof(dp));
50     for (int i=1; i<=n; i++)
51         if (ind[i]==0 && out[i]!=0)
52             ans+=dfs(i);
53     printf("%d
", ans);
54     return 0;
55 }