洛谷 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_u1dpu​1状态转移方程策略集合从入度为0的顶点出发到达顶点v的所有路径分割策略集合根据到达顶点v的前一个顶点的不同情况分割策略集合。设模数M 80112002 M80112002M80112002如果到达顶点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​}modME EE为图的边集。 u , v ∈ E u,v \in Eu,v∈E表示图中存在边u, v。要想先访问所有到顶点v有边的顶点u再访问顶点v需要按照拓扑排序的顺序访问各个顶点。在拓扑排序的过程中进行动规即可求出状态数组d p dpdp。最后遍历所有顶点对出度为0的顶点的路径数加和并对模数取模即可得到本题的答案。遍历所有顶点的过程可以写for循环遍历所有顶点的编号也可以在拓扑排序过程中顶点出队时对出队的顶点做处理。拓扑排序的过程也是对图中顶点遍历的过程。【题解代码】解法1拓扑排序动规#includebits/stdc.h#defineINF0x3f3f3f3fusingnamespacestd;constintN5005,M80112002;vectorintedge[N];//edge[i]顶点i的邻接点intn,m,degIn[N],degOut[N],dp[N],ans;//dp[i]从入度为0的顶点到顶点i的路径数量voidtopoSort(){queueintque;for(inti1;in;i)if(degIn[i]0){que.push(i);dp[i]1;}while(!que.empty()){intuque.front();que.pop();if(degOut[u]0)//拓扑排序的过程也是对图遍历的过程u出队时dp[u]已经求好了。ans(ansdp[u])%M;for(intv:edge[u]){dp[v](dp[v]dp[u])%M;if(--degIn[v]0)que.push(v);}}}intmain(){intf,t;cinnm;for(inti1;im;i){cinft;edge[f].push_back(t);degIn[t],degOut[f];//degIn[i]顶点i的入度 degOut[i]顶点i的出度}topoSort();coutans;return0;}