洛谷P4017 最大食物链计数题解

给你一个食物网，你要求出这个食物网中最大食物链的数量。

（这里的“最大食物链”，指的是 生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。 ）

由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。

第一行，两个正整数 n、m，表示生物种类 n 和吃与被吃的关系数 m。

接下来 m 行，每行两个正整数，表示被吃的生物A和吃A的生物B。

5 7 
1 2
1 3
2 3
3 5
2 5
4 5
3 4

5

本题给出一个单向连通图，需要输出图中所有入度为零的点到所有出度为零的点的路径数之和，如果不了解以上有关图的名词可以自行去搜索一下。

还是蒟个栗子吧，就拿样例来说：

终点为点1的路径数为0，所以点1入度为0；

起点为点5的路径数为0，所以点5出度为0.

所以，题目所求的就是从点1到点5的路径总数，结果为5.

1-->2-->5
1-->2-->3-->5
1-->2-->3-->4-->5
1-->3-->4-->5
1-->3-->5

我们使用 in[i] 表示点i的入度数，out[i] 表示点i的出度数，a[i][n] 表示第n条以点i为起点的路径的终点。

不难发现，到某点的路径总数取决于，到 以这个点为终点的路径的起点 的路径数之和，用状态转移方程表示为
num[ i ] = num[ k1 ] + num[ k2 ] + ··· + num[ kn ]（其中 k1 , k2 ··· kn表示以点 i 为终点的路径的起点）

如何实现呢？通过递推

我们从第入度为0的点开始递推，将所有与入度为0的点相连的点路径数都加上入度为0点的路径数，并将已经处理过后的点入度减一，这样在新一轮的遍历中就会出现新的一些入度为0的点，直到处理完所有的点后，将所有出度为0的值的点之和输出即可。

这里注意，因为数据量过大，要求对80112002取模，所以在进行更新时，要多次取模，防止超出数据范围。

#include
using namespace std;
int n,m,ans,x,y;
int lea;//未处理的数
int a[5005][5005];
int in[5005],out[5005];
bool b[5005];//标记是否处理
long long num[5005];
int main()
{
    cin>>n>>m;
    lea=n;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        a[x][++out[x]]=y;//存储
        in[y]++;//y入度加一
    }
    for(int i=1;i<=n;i++)
        if(!in[i])
            num[i]++;//将所有入度为0的点加一，表示同一个点的路径数为0
    while(lea)//当还有未处理的数时
    {
    for(int i=1;i<=n;i++)
        if(!in[i]&&!b[i])
        {
            b[i]=1;
            for(int j=1;j<=out[i];j++)
            {
                num[a[i][j]]+=num[i];
                num[a[i][j]]%=80112002;
                in[a[i][j]]--;//该点入度数减一
            }
            lea--;//为处理的数减一
        }
    }
    for(int i=1;i<=n;i++)
        if(!out[i])
        {
            ans+=num[i];//取所有入度为0的点之和
            ans%=80112002;//取模
        }
    cout< 
PS：写完才发现，这应该也算一种dp。。