web analytics

BZOJ1179 Atm //缩点+spfa

1179: [Apio2009]Atm

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的单向的道路到达其中的至少一个酒吧。

分析:

这道题其实很迷。首先这道题发现如果在一个强连通分量里面,都可以走到,而且也没有限制走的次数,所以我们可以将在强连通分量里面的点,缩成一个全新的点。之后造出来一个全新的图。boom!新造出来的图可以走一遍最短路spfa。就好了。

至于怎么缩点。
用并查集先找到父亲与儿子。之后每次判断出一个强量通分量就用将他们的父亲全连成第一个数。
之后在新建图(如果一个点的父亲与儿子的父亲不相同,那他们1,连上2,建边)
这个边其实可以重复利用。这样可以节省空间。

Post a Comment

You must be logged in to post a comment.