首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
flymouse专题
poj 3160 Father Christmas flymouse 强连通+dp
首先我们可以确定的是,对于val值小于0的节点都变成0. 假设一个集合内2个房间都能任意到达,那么我就可以吧集合内的所有点的价值都取到,并且可以达到任一点。实际上集合内的每个点是相同的,这样的集合就是一个强连通分量。 那么我们就可以用tarjin算法进行强连通缩点, 最后形成一个dag的图。在dag的图上面进行dp。可以先用拓扑排序后dp。或者建反响边记忆化搜索 。 VIEW
阅读更多...