缩点-将图转化为 DAG 跑 DP ：P1455，P2169

之前有提到，缩点可以将一张有向图转化为一张有向无环图（DAG），这样我们就可以在图上跑 DP 了。而我们实现 DP 的手段一般是在拓扑排序中实现，有时候也会用到最短路。

P1455

https://www.luogu.com.cn/problem/P1455

题目暗示很明显，物品会有依赖关系，于是我们把有依赖关系的物品两两连边，缩点并记录每一个强连通分量的代价与价值，接下来就是跑 01 背包。当然这个缩点的过程也可以用并查集代替。这个题看起来是无向边，但是这不影响，把它看作两条有向边即可。

P2169

https://www.luogu.com.cn/problem/P2169

这，啊，本地连接就是在一个环里面，缩成一个点就可以了，然后其他的就是有边权的。这完全可以写一个拓扑排序跑 DP，但是当时莫名其妙地写了一个 Dij。