BZOJ 1179: [Apio2009]Atm Tarjan强连通分量缩点，SPFA，DP

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

解题方法： 首先进行强连通缩点，维护每一个连通分量中，是否有一个点是酒吧，以及总钱数的多少。对缩点后的图进行拓扑排序，然后按照拓扑排序进行动态规划。记 dp[i]表示走到点 i 的最大获利，对于给定的起点属于的连通块有 dp[i]＝money[i]，其余点的初值都是 dp[i]＝负无穷。对于一条边 i 连接 j，我们用 dp[i]＋money[j]来更新 dp[j]。答案是满足一个连通块中至少有一个是酒吧的强连通分量中最大的 dp[i]。由于会爆栈，强连通分量算法要进行人工堆栈。时间复杂度 O(n＋m)。