题解 | #[HAOI2016]食物链#

呜呜呜，本人第一道正经的图论题

核心：记忆化搜索+拓扑排序
大概题意：初中知识，能量只能由低级流向高级，所以我们要找到并记录下最底层的生产者，也就是入读为0的点——（没有能量来源的那个）；
这道题用临接链表存图好处理一点点，（好吧，就是不太会写链式前向星）；
先讲讲记忆化储存，其实这就是一个用空间来换时间的行为，当我们dfs过的点如果把它记住，在下一次dfs遇到它的时候直接返回值，这样就会省下很多的时间。这道题如果没有记忆化搜索直接dfs的话，会超时，大家可以试一试
注意：众所周知，如果只有一个动物的话，是没有办法形成食物链的；

int dfs(int now,int level)
{
    if(memory[now]!=-1)return memory[now];
    if(a[now].size()==0)
    {
    if(level!=1) return 1;    
    else return 0;//判断是否为一种动物；
    }
    long long sum=0; 
    for(int i=0;i<a[now].size();i++)
    {sum+=dfs(a[now][i],level+1);}
    return memory[now]=sum;
}

最后贴上AC代码

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
vector <int> a[1000000];
int vis[1000000];
int memory[1000000];

int dfs(int now,int level)
{
    if(memory[now]!=-1)return memory[now];
    if(a[now].size()==0)
    {
    if(level!=1)return 1;        
    else return 0;
    }
    long long sum=0; 
    for(int i=0;i<a[now].size();i++)
    {
        sum+=dfs(a[now][i],level+1);
    }
    return memory[now]=sum;
}
int main(){    
    int n,m;
    cin>>n>>m;
    int x,b;
    memset(vis,-1,sizeof(vis));
    memset(memory,-1,sizeof(memory));
    for(int i=0;i<m;i++)
    {
        cin>>x>>b;
        a[x].push_back(b);
        vis[b]++;
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==-1){//如果没有动物对他能量输入的话就是-1；因为我初始化的是-1，大家可以直接用0；
            ans+=dfs(i,1);
        }
    }
    cout<<ans<<"\n";
    return 0;
}