BZOJ 4562 食物链【记忆化搜索啊】

Description

Input

Output

一个整数即食物网中的食物链条数

Sample Input

Sample Output

思路：

1、一开始在网上还找到了一个公式：食物链条数=分叉边数-分叉点数+1....

尼玛大骗纸不好用啊、分叉到两个子树中就尼玛不是一个东西了好伐。

2、统计计数问题考虑dp，设定dp【i】表示以i为根的子树食物链的条数。

那这个题就是水题啊，dp【i】=Σdp【v】；

然后设定个超级源点连度为0的所有节点，那么dp【0】就是答案啊。

3、注意孤立节点不算答案啊。就没了啊。

Ac代码：

#include<stdio.h>#include<string.h>#include<vector>using namespace std;vector<int >mp[100600];int degree[100600];int dp[100600];int n,m;int Dfs_Dp(int u){    if(dp[u]==-1)    {        dp[u]=0;        int size=mp[u].size();        for(int i=0;i<size;i++)        {            int v=mp[u][i];            dp[u]+=Dfs_Dp(v);        }        if(size==0)dp[u]=1;        return dp[u];    }    else return dp[u];}int main(){    while(~scanf("%d%d",&n,&m))    {        memset(dp,-1,sizeof(dp));        memset(degree,0,sizeof(degree));        for(int i=0;i<=n;i++)mp[i].clear();        for(int i=0;i<m;i++)        {            int x,y;            scanf("%d%d",&x,&y);            mp[x].push_back(y);            degree[y]++;        }        for(int i=1;i<=n;i++)        {            if(degree[i]==0&&mp[i].size()>0)mp[0].push_back(i);        }        if(mp[0].size()>0)        Dfs_Dp(0);        if(dp[0]<0)dp[0]=0;        PRintf("%d/n",dp[0]);    }}