题目描述

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定, 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是,Siruseri 的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。

Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发,沿着单向道路行驶,抢劫所有他途径的 ATM 机,最终他将在一个酒吧庆 祝他的胜利。

使用高超的黑客技术,他获知了每个 ATM 机中可以掠取的现金数额。他希 望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可 以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后,该 ATM 机 里面就不会再有钱了。

市中心在路口 1,由一个入口符号→来标识,那些有酒吧的路口用双圈来表

示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中,Banditji 能抢 劫的现金总数为 47,实施的抢劫路线是:1-2-4-1-2-3-5。


 

solution

Tarjan板子题..

“他可 以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后,该 ATM 机 里面就不会再有钱了。 ”

实际上的意思是对于同一个连通块,他可以获得等价于连通块价值总和的现金

对于缩点后有酒吧的连通块,显然可以作为终点,

那么用Tarjan缩点后SPFA求一遍最长路就行了

Ps:上周有人问过我这道题为什么会一直RE,我交了一遍Ac过的代码发现迷のRE,后来知道是新云端的锅。

 

分类: 图论题解

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
youming Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
youming
游客
youming

%%%