【BZOJ1179】[Apio2009]Atm/抢掠计划-布布扣-bubuko.com

1179: [Apio2009]Atm

Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 4701 Solved: 2087
[Submit][Status][Discuss]

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个 Siruser

i 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。Bandit

ji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他

途径的 ATM 机，最终他将在一个酒吧庆祝他的胜利。使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的

现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口

或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机里面就不会再有钱了。例如，假设该城中有 6 个

路口，道路的连接情况如下图所示：

市中心在路口 1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表示。每个 ATM 机中可取的钱数标在了

路口的上方。在这个例子中，Banditji 能抢劫的现金总数为 47，实施的抢劫路线是：1-2-4-1-2-3-5。

第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。

接下来M行，每行两个整数，这两个整数都在1到N之间，

第i+1行的两个整数表示第i条道路的起点和终点的路口编号。

接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。

接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。

接下来的一行中有P个整数，表示P个有酒吧的路口的编号

N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。

输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6

Solution:

这题其实蛮有意思的，正好复习tarjan算法了。

tarjan算法流程:

dfn数组记录第一次dfs的时间，low数组记录搜索回栈内最早元素的dfn值。

于是有$low[u]=min(low[v],dfn[v],dfn[u])$

话说回来，low不一样的节点也可以在同一个联通块内，这点我需要翻算法导论。

回到这个题目，对于这个题目，我们不难发现如果他走环相当于走了一个点，于是我们就把这些点缩成scc，重构图，然后跑一遍spfa求出每个有酒吧的scc里的最大值（最长路），之后判一遍。

时间复杂度:$O(n+n+m)$，因为这里缩完点之后相当于是拓扑排序了（因为图变成了DAG）。

不过话说回来我拓扑排序还没复习……

原文：https://www.cnblogs.com/redwind/p/9473472.html