[HAOI2016]食物链

[HAOI2016]食物链

考点: 拓扑排序 ， 记忆化搜索

题目大意

就题目本意吧

分析

这题暴力的做法可以得到70分，于是我们考虑怎么优化过程。我们发现每个节点向下的路径分支其实已经是固定好了的。但是在从入度为 0 的点进行dfs的时候会大量的访问重复节点，于是我们考虑使用记忆化的方法将已经计算过具有答案的结点记录下来。

int dfs(int now,int level)
{
    if(dp[now] != -1)return dp[now];
    if(a[now].size() == 0)
    {
        if(level == 1)return 0;
        return 1;
    }
    int sum = 0;
    for(int i = 0;i < a[now].size() ;i ++)
        sum += dfs(a[now][i] , level + 1);
    return dp[now] = sum;
}

需要注意的点:

• 注意只有 1 个生物的时候不算一条食物链。所以要进行特判，在这里我们只需要判断层数即可

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int in[N];
int n , m , cnt ,dp[N];
vector<int> a[N];
int dfs(int now,int level)
{
    if(dp[now] != -1)return dp[now];
    if(a[now].size() == 0)
    {
        if(level == 1)return 0;
        return 1;
    }
    int sum = 0;
    for(int i = 0;i < a[now].size() ;i ++)
        sum += dfs(a[now][i] , level + 1);
    return dp[now] = sum;
}
int main()
{
    memset(dp , -1 , sizeof dp);
    cin >> n >> m;
    int x , y;
    for(int i = 0;i < m;i ++)
    {
        cin >> x >> y;
        a[x].push_back(y);in[y]++;
    }
    for(int i = 1;i <= n;i ++)
        if(in[i] == 0)cnt += dfs(i , 1);
    cout << cnt << endl;
    return 0;
}