BZOJ_1179_[Apio2009]Atm_tarjan+spfa
题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1179
分析：
显然有环没法直接最长路，那就缩个点再跑。
酒吧连汇点。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 500050
int head[N],to[N<<1],nxt[N<<1],val[N],can[N],cancan[N];
int n,m,bel[N],dfn[N],low[N],st[N],top,scc,tot,cnt,S,T;
int ins[N],sum[N],X[N],Y[N],Q[N],l,r,dis[N],inq[N];
inline void add(int u,int v){
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void tarjan(int x){
st[top++]=x;ins[x]=1;dfn[x]=low[x]=++tot;
for(int i=head[x];i;i=nxt[i]){
if(!dfn[to[i]]){
tarjan(to[i]);
low[x]=min(low[x],low[to[i]]);
}else if(ins[to[i]])low[x]=min(low[x],dfn[to[i]]);
}
if(dfn[x]==low[x]){
int t=st[--top];ins[t]=0;
bel[t]=++scc;
sum[scc]+=val[t];
cancan[scc]|=can[t];
while(t!=x){
t=st[--top];ins[t]=0;
bel[t]=scc;
sum[scc]+=val[t];
cancan[scc]|=can[t];
}
}
}
int main(){
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y);
X[i]=x,Y[i]=y;
}
for(int i=1;i<=n;i++){
scanf("%d",&val[i]);
}
scanf("%d%d",&S,&x);
T=n+1;
for(int i=1;i<=x;i++){
scanf("%d",&y);
can[y]=1;
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
memset(head,0,sizeof(head));cnt=0;
for(int i=1;i<=m;i++){
if(bel[X[i]]!=bel[Y[i]])add(bel[X[i]],bel[Y[i]]);
}
for(int i=1;i<=scc;i++)if(cancan[i])add(i,T);
S=bel[S];
Q[r++]=S;inq[S]=1;dis[S]=sum[S];
while(l^r){
int x=Q[l++];inq[x]=0;if(l==n+10)l=0;
for(int i=head[x];i;i=nxt[i]){
if(dis[to[i]]<dis[x]+sum[to[i]]){
dis[to[i]]=dis[x]+sum[to[i]];
if(!inq[to[i]]){
inq[to[i]]=1;Q[r++]=to[i];if(r==n+10)r=0;
}
}
}
}
printf("%d",dis[T]);
}