G004 DAG DP P1685 游览 P4017 食物链计数如何最大化？

P1685 游览 - 洛谷 P4017 最大食物链计数 - 洛谷 已知一个 DAG 和起点 \(s\) 终点 \(e\) 和从终点回起点的时间 \(t\) ，如果从起点到终点如果有多条可选择的路径，那么要全部走一遍。问总耗时多少（对 \(10000\) 取模）。 假如从 \(e\) 回到 \(s\) 的次数为 \(cnt_e\) ，不难看出返回起点的总时间为 \((cnt_e-1)\times t\) 。 初始化 \(cnt_s=1\) 其余为 \(0\) 按转移方程 cnt[v] += cnt[u] 递推 初始化 \(dp\) 数组定义为从起点到当前节点的总距离，转移方程为 dp[v] += dp[u] + cnt[u] * w 。 看图片更好理解第二个转移方程 转移方程执行流程图 具体代码为 import sys from collections import deque from math import inf if 1: inp = lambda: sys.stdin.readline().strip() II = lambda: int(inp()) MII = lambda: map(int, inp().split()) LII = lambda: list(MII()) Max = lambda x, y: x if x > y else y Min = lambda x, y: x if x < y else y def main(): n, m, s, e, t = MII() g = [[] for _ in range(n + 1)] din = [0] * (n + 1) for _ in range(m): u, v, w = MII() g[u].append((v, w)) din[v] += 1 dq = deque([i for i in range(1, n + 1) if din[i] == 0]) cnt = [0] * (n + 1) cnt[s] = 1 dp = [0] * (n + 1) while dq: u = dq.popleft() for v, w in g[u]: cnt[v] += cnt[u] dp[v] += dp[u] + cnt[u] * w din[v] -= 1 if din[v] == 0: dq.append(v) ans = (cnt[e] - 1) * t + dp[e] print(ans % 10000) if __name__ == "__main__": main() 第二道题要比上一道简单，这里只需要统计经过多少次即可，初始化所有源点为 \(1\) 转移方程为前面的第一个转移方程 dp[v] += dp[u] 唯一要注意的点是结果是所有汇点的和。