一、演算法介紹 tarjan——求解有向圖強連通分量。這個演算法在本人的一篇blog中有介紹,這裡就不贅述了。貼上介紹tarjan的的blog鏈接:http://www.cnblogs.com/Maki-Nishikino/p/5866191.html 那麼接下來說說SPFA: SPFA全稱Shorte ...
一、演算法介紹
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