Rhythm of Codes

BZOJ 1179]ATM题解 Tarjan缩点+SPFA

 

Description

 

 

Input

第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数,表示P个有酒吧的路口的编号

 

Output

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

 

Sample Input

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

Sample Output

47

HINT

50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

 

 

 

观察题目即可发现:1->2->4是一个强连通分量,3,5,6是一个强连通分量。很明显这是一道强连通分量的裸题。使用tarjan或各种神奇的求强连通分量的算法所完点后,剩下的就可以用各种算法来乱搞了。

 

先是tarjan求强连通分量部分

求完强连通分量,需要缩点建新图。注意:加边的时候变量名别搞混了。

 

接下来读题,既然要使得抢的钱最多,那么我们可以把它转化成一个最大路问题,用spfa求出源点到各点的最大距离,再判断各点是否是酒吧(符合要求的节点)。

 

以下是完整代码

 

顺手赠送一套数据点

 

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *