Day 1
有向无环图
- 一种特殊的有向图，没有任何环，简写为 DAG。
- 对于这种图，我们就有“拓扑序”。
拓扑序不是唯一解。
拓扑排序流程：每次删去一个没有入度的点加入拓扑序中，如此重复下去即可。
P1807 最长路
题目描述：设 \(G\) 为有 \(n\) 个顶点的带权有向无环图，\(G\) 中各个顶点的编号为 \(1\) 到 \(n\)。计算图 \(G\) 中 \(<1,n>\) 间的最长路径。
解法：令 \(f(i)\) 表示 \(i\) 到 \(n\) 的最长路径长度。
那么 $$f(a) = \max(f(t_0)+w_{a_{t_0}},f(t_1)+w_{a_{t_1}},\cdots,f(t_k)+w_{a_{t_k}})$$