SPFA算法
- SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法。
- 判负环（在差分约束系统中会得以体现）。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
tarjan算法
Tarjan算法是用来求有向图的强连通分量的。
Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。
当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。
BZOJ 1179
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
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的单向的道路到达其中的至少一个酒吧。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; int n,m,st,p;
int ans;
int money[],moneys[];
int q[],b,e,d[];//spfa
int stack[],dfn[],low[],index,top;//tarjan
bool vis[];
int color[],num; struct node{
int u;
int v;
int next;
}s[],map[];
int head[],rehead[],cnt; void add(int x,int y){
s[++cnt].u=x;
s[cnt].v=y;
s[cnt].next=head[x];
head[x]=cnt;
} void tarjan(int x){
dfn[x]=++index;
low[x]=index;
stack[++top]=x;
vis[x]=true; for(int i=head[x];i!=;i=s[i].next){
if(!dfn[s[i].v]){
tarjan(s[i].v);
low[x]=min(low[x],low[s[i].v]);
}
else if(vis[s[i].v]==true)low[x]=min(low[x],dfn[s[i].v]);
} if(dfn[x]==low[x]){
vis[x]=false;
color[x]=++num;//计算个数
while(stack[top]!=x){
color[stack[top]]=num;
vis[stack[top--]]=false;
}
top--;
}
} void rebuild(){//缩点
cnt=;
for(int i=;i<=n;i++){
for(int j=head[i];j!=;j=s[j].next){
if(color[i]!=color[s[j].v]){
map[++cnt].u=color[i];
map[cnt].v=color[s[j].v];
map[cnt].next=rehead[color[i]];
rehead[color[i]]=cnt;
}
}
}
} void spfa(int x){
memset(vis,false,sizeof(vis));
q[++b]=x;
e++;
vis[x]=true;
d[x]=moneys[x];
while(b<=e){
int y=q[b++];
for(int i=rehead[y];i!=;i=map[i].next){
if(d[map[i].v]<d[y]+moneys[map[i].v]){
d[map[i].v]=d[y]+moneys[map[i].v];
if(!vis[map[i].v]){
q[++e]=map[i].v;
vis[map[i].v]=true;
}
}
}
vis[q[b]]=false;
}
} int main(){ scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
} for(int i=;i<=n;i++)
if(!dfn[i])tarjan(i); rebuild();//重建图 for(int i=;i<=n;i++){
scanf("%d",&money[i]);
moneys[color[i]]+=money[i];
} scanf("%d%d",&st,&p); spfa(color[st]); for(int i=;i<=p;i++){
int a;
scanf("%d",&a);
ans=max(ans,d[color[a]]);
}
printf("%d",ans); return ;
}