logo
publist
写文章

简介

该用户还未填写简介

擅长的技术栈

可提供的服务

暂无可提供的服务

洛谷 P3627 [APIO2009] 抢掠计划 Kosaraju

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

文章图片
#算法#数据结构
到底了