洛谷 P4017 最大食物链计数

【题目链接】

洛谷 P4017 最大食物链计数

【题目考点】

1. 有向无环图动规，拓扑排序

【解题思路】

每个生物是一个顶点。
如果A被B吃，或者说B吃A，那么A到B有一条有向边，有向边的方向代表能量流动的方向。
食物链构成的网中一定没有环，该图是有向无环图。
一条食物链的左端是“不会捕食其他生物的生产者”，即它不会吃其它生物，不会有能量流向该生物，那么其它顶点到“生产者”顶点没有边，即“不会捕食其他生物的生产者”顶点的入度为0。
一条食物链的右端是“不会被其他生物捕食的消费者”，即该生物的能量不会流向其它生物，那么该顶点到其它顶点没有边，即“不会被其他生物捕食的消费者”顶点的出度为0。

该题求从图中入度为0的顶点到出度为0的顶点的路径数量。

状态定义

• 阶段：到达某个顶点
• 决策：下一步到哪个邻接点
• 策略：路径
• 策略集合：从入度为0的顶点出发到达某顶点的所有路径
• 统计量：路径数

状态定义d p i dp_idpi​：从入度为0的顶点出发到达顶点i的路径数。
对于入度为0的顶点u，到达顶点u的路径数为1，因此d p u = 1 dp_u=1dpu​=1

状态转移方程

• 策略集合：从入度为0的顶点出发到达顶点v的所有路径
• 分割策略集合：根据到达顶点v的前一个顶点的不同情况分割策略集合。

设模数M = 80112002 M=80112002M=80112002
如果到达顶点v的前一个顶点为顶点u，顶点u到顶点v有一条边<u, v>。
那么每条到达顶点u的路径，在加上边<u, v>，都可以形成一条到达顶点v的路径。
到达顶点v的路径的数量需要增加到达顶点u的路径的数量，再对模数M取模。
对于每个到v有边的顶点u，都需要让到达顶点v的路径数量增加到达顶点u的路径数。
因此状态转移方程为：d p v = ∑ < u , v > ∈ E { d p u } m o d M dp_v = \sum\limits_{<u,v>\in E}\{dp_u\}\bmod Mdpv​=<u,v>∈E∑​{dpu​}modM
E EE为图的边集。< u , v > ∈ E < u,v >\in E<u,v>∈E表示图中存在边<u, v>。

要想先访问所有到顶点v有边的顶点u，再访问顶点v，需要按照拓扑排序的顺序访问各个顶点。在拓扑排序的过程中进行动规，即可求出状态数组d p dpdp。

最后遍历所有顶点，对出度为0的顶点的路径数加和并对模数取模，即可得到本题的答案。
遍历所有顶点的过程，可以写for循环遍历所有顶点的编号，也可以在拓扑排序过程中顶点出队时对出队的顶点做处理。拓扑排序的过程也是对图中顶点遍历的过程。

【题解代码】

解法1：拓扑排序+动规

#include<bits/stdc++.h>#defineINF0x3f3f3f3fusingnamespacestd;constintN=5005,M=80112002;vector<int>edge[N];//edge[i]：顶点i的邻接点intn,m,degIn[N],degOut[N],dp[N],ans;//dp[i]：从入度为0的顶点到顶点i的路径数量voidtopoSort(){queue<int>que;for(inti=1;i<=n;++i)if(degIn[i]==0){que.push(i);dp[i]=1;}while(!que.empty()){intu=que.front();que.pop();if(degOut[u]==0)//拓扑排序的过程也是对图遍历的过程，u出队时dp[u]已经求好了。ans=(ans+dp[u])%M;for(intv:edge[u]){dp[v]=(dp[v]+dp[u])%M;if(--degIn[v]==0)que.push(v);}}}intmain(){intf,t;cin>>n>>m;for(inti=1;i<=m;++i){cin>>f>>t;edge[f].push_back(t);degIn[t]++,degOut[f]++;//degIn[i]：顶点i的入度 degOut[i]：顶点i的出度}topoSort();cout<<ans;return0;}