
简介
该用户还未填写简介
擅长的技术栈
未填写擅长的技术栈
可提供的服务
暂无可提供的服务
洛谷 P3627 [APIO2009] 抢掠计划 Kosaraju
初看题,可能想到用BFS遍历图,然后将每次取完钱之后的结果累计,遇到酒吧就更新答案值。但是,本题为直接使用BFS必然会导致死循环,而标记每个走过的节点,又不能维护后来的值优于先来的值的情况。于是,需要先对强联通分量并入一个集合中进行(即让多个可以相互到达的点看作一个整体),之后就可以开心的用BFS处理了。关于缩点处理,本文采用的是算法,即用两遍DFS预处理图:第一次 DFS,选取任意顶点作为起点,

到底了







