[刷题笔记] Luogu P3183 食物链

Problem

Description

通俗一点就是在一张图上求入度为0的点到出度为0的点路径的个数。

Solution

简要题意后发现可以拓扑排序？这里主要介绍记忆化搜索。

记忆化搜索是指记住当前节点的状态，待下次搜到这里直接调用即可，无需继续搜索。
显然由记忆化搜索延伸到dp，但如果状态设计很复杂记忆化搜索即可。

存图的时候记录一下每个点的入度和出度，dfs时如果该点出度为0，则代表一条食物链，返回1即可。
最后求答案时只需要找入度为0但是出度不为0的点开始dfs即可（单独的一个点不算）

具体实现见代码：

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 10010
using namespace std;
int dp[N];
int n,m;
int mapp[N][N];
vector <int> Edge[N];
int rem[N];
int ans = 0;
int in[N],out[N];
int dfs(int x)
{
    if(rem[x]) return rem[x]; //记忆化
    int sum = 0;
    if(out[x] ==0 ) return 1; //如果出度为0则代表顶级消费者返回1即可
    for(int i=0;i<Edge[x].size();i++)
    {
        sum += dfs(Edge[x][i]); //计算该节点食物链个数
    }
    rem[x] = sum; //记忆化
    return sum; //记忆化后返回该节点食物链个数
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        Edge[x].push_back(y);
        in[y] ++; //记录入度出度
        out[x] ++;
    }
    for(int i=1;i<=n;i++) 
    {
        if((in[i]==0&&out[i]!=0)) //如果入度为0但是出度不为0则代表生产者开始dfs
            ans += dfs(i);
    }
    cout<<ans<<endl;
    return 0;
}