【Tarjan】+【SPFA】【APIO2009】Atm，tarjanspfa
一、算法介紹
tarjan——求解有向圖強連通分量。這個算法在本人的一篇blog中有介紹，這裡就不贅述了。貼上介紹tarjan的的blog鏈接：http://www.cnblogs.com/Maki-Nishikino/p/5866191.html
那麼接下來說說SPFA：
SPFA全稱Shortest Path Faster Algorithm，用於求解單源最短路。既然名字中有“Faster”，那它就一定有過人之處，事實上它也的確比Dijkstra和Bellman-Ford更高效。
它的思路大致如下：
1、先用鄰接表把圖存下來，並且規定一個數組d，d[i]表示起點到i的最短路程；
2、建立一個隊列，將起點放入隊列；
3、對隊首元素執行松弛操作，遍歷所有以隊首元素為起點的邊，如果被遍歷的邊可以使到被遍歷的邊的終點的路徑變短，那麼就更新這個最短路徑，並把被遍歷的邊的終點放到隊尾；
4、每完成一次松弛，就令隊首元素出隊，重復2，直到隊列裡沒有元素。
原諒博主懶得貼偽代碼，我就直接講題了，反正題解裡也有模板#手動滑稽
二、APIO2009 Atm題解
原題鏈接（來自bzoj）：http://www.lydsy.com/JudgeOnline/problem.php?id=1179
題目描述：
輸入：
第一行包含兩個整數N、M。N表示路口的個數，M表示道路條數。接下來M行，每行兩個整數，這兩個整數都在1到N之間，第i+1行的兩個整數表示第i條道路的起點和終點的路口
編號。接下來N行，每行一個整數，按順序表示每個路口處的ATM機中的錢數。接下來一行包含兩個整數S、P，S表示市中心的編號，也就是出發的路口。P表示酒吧數目。接下來
的一行中有P個整數，表示P個有酒吧的路口的編號。
輸出：
輸出一個整數，表示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
樣例輸出：
47
數據范圍：
50%的輸入保證N, M<=3000。所有的輸入保證N, M<=500000。每個ATM機中可取的錢數為一個非負整數且不超過4000。輸入數據保證你可以從市中心沿著Siruseri的單向的道路到達其中的至少一個酒吧。
對於這道題，我們考慮先用tarjan求出它的所有強連通分量，再把同一個強連通分量上的ATM機的錢加起來，讓一個強連通分量上的點縮成一個點。然後以市中心s為起點，用SPFA跑出s到其他點的最長（最有價值）路，比較酒吧所在點的d值，輸出大的即可。
附上代碼：
![]()
1 #include<stdio.h>
2 #include<algorithm>
3 #include<string.h>
4 using namespace std;
5 struct node
6 {
7 int v;
8 int next;
9 };
10 int n,m;
11 node e[500010],map[500010];//鄰接表存圖
12 int st[500010],head[500010],cnt;
13 int atm[500010],money[500010];
14 int d[500010],q[500010];//最短路徑＆SPFA要用的隊列
15 void build(int a,int b)
16 {
17 e[++cnt].v=b;
18 e[cnt].next=st[a];
19 st[a]=cnt;
20 }//建圖找強連通分量
21 int stack[500010],top;//tarjan需要的棧
22 int dfn[500010],low[500010],dex;//時間戳（深搜序）、可回溯到的最早棧中時間戳、次序編號
23 bool vis[500010];//tarjan時判斷點是否在棧中，SPFA時判斷點是否在隊列中
24 int color[500010],num;//表示同一強連通分量上的點
25 void tarjan(int x)//tarjan找強連通分量
26 {
27 dfn[x]=++dex;
28 low[x]=dex;
29 vis[x]=true;
30 stack[++top]=x;//當前點入棧
31 int i;
32 for(i=st[x];i!=0;i=e[i].next)//枚舉以當前點為起點的邊
33 {
34 int temp=e[i].v;//temp為當前被枚舉邊的終點
35 if(!dfn[temp])//如果當前邊終點未被處理
36 {
37 tarjan(temp);
38 low[x]=min(low[x],low[temp]);
39 }
40 else if(vis[temp])low[x]=min(low[x],dfn[temp]);
41 }
42 if(dfn[x]==low[x])
43 {
44 vis[x]=false;
45 color[x]=++num;//標記當前強連通分量內的點
46 while(stack[top]!=x)//棧頂元素依次出棧
47 {
48 color[stack[top]]=num;
49 vis[stack[top--]]=false;
50 }
51 top--;
52 }
53 }
54 void add()// 把同一強連通分量上的點縮成一個點，把這些點連成一張新圖
55 {
56 cnt=0;
57 int i,j;
58 for(i=1;i<=n;i++)
59 {
60 for(j=st[i];j!=0;j=e[j].next)
61 {
62 int temp=e[j].v;
63 if(color[i]!=color[temp])
64 {
65 map[++cnt].v=color[temp];
66 map[cnt].next=head[color[i]];
67 head[color[i]]=cnt;
68 }
69 }
70
71 }
72 }
73 void spfa(int x)//SPFA找最長路
74 {
75 memset(vis,false,sizeof(vis));
76 int l=1,r=1;
77 q[l]=x;//初始點放入隊列
78 vis[x]=true;
79 d[x]=money[x];
80 while(l<=r)
81 {
82 int u=q[l++];
83 for(int i=head[u];i!=0;i=map[i].next)//遍歷所有以當前點為起點的邊
84 {
85 int v=map[i].v;
86 if(d[v]<d[u]+money[v])
87 {
88 d[v]=d[u]+money[v];
89 if(vis[v])continue;
90 q[++r]=v;//如果當前拓展的邊的終點不在隊列裡，就把它放入隊尾
91 vis[v]=true;
92 }
93 }
94 vis[u]=false;
95 }
96 }
97 int main()
98 {
99 int a,b,i,s,p,o,ans=0;
100 scanf("%d%d",&n,&m);
101 for(i=1;i<=m;i++)
102 {
103 scanf("%d%d",&a,&b);
104 build(a,b);
105 }//建初始圖
106 for(i=1;i<=n;i++)
107 {
108 if(!dfn[i])tarjan(i);//找強連通分量
109 }
110 add();//建新圖
111 for(i=1;i<=n;i++)
112 {
113 scanf("%d",&atm[i]);
114 money[color[i]]+=atm[i];
115 }
116 scanf("%d%d",&s,&p);
117 spfa(color[s]);//找單源最短路
118 for(i=1;i<=p;i++)
119 {
120 scanf("%d",&o);
121 ans=max(ans,d[color[o]]);//找到以酒吧為終點的最長路
122 }
123 printf("%d",ans);
124 return 0;
125 }
APIO2009 Atm
