首页 > 代码库 > [BZOJ 1295][SCOI2009]最长距离(SPFA+暴力)

[BZOJ 1295][SCOI2009]最长距离(SPFA+暴力)

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1295

分析:很巧妙的一道spfa
从搜索的角度是搜索在所有1中搜索删除哪T个1,对整个图询问,这样肯定TLE

不妨反过来想一想:对于两个点,弄出联通这两个点所需删除的最少的1,那么就知道这两个点是否可以作为题目要求的起点和终点,如果满足算一下结果和ans比较一下就可以。

所以算法就出来了:

枚举起点(S,T),用SPFA跑出图上的所有点到起点这条路径联通的最少删除的1,那么ans=max(dist(起点,i)) (其中i到起点的删除最少的1的数量<=T)

 

[BZOJ 1295][SCOI2009]最长距离(SPFA+暴力)