明明优化了spfa还是好慢……
因为只能取一次值，所以先tarjan缩点，把一个scc的点权和加起来作为新点的点权，，然后成立新图。在新图上跑spfa最长路，最后把酒吧点的dis取个max就是答案。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=500005,inf=1e9; int n,m,h[N],cnt,dis[N],st,p,a[N],b[N],ans,dfn[N],low[N],tot,bl[N],col,s[N],top,x[N],y[N],va[N]; bool v[N]; struct qwe { int ne,to; }e[N]; int read() { int r=0,f=1; char p=getchar(); while(p<‘0‘||p>‘9‘) { if(p==‘-‘) f=-1; p=getchar(); } while(p>=‘0‘&&p<=‘9‘) { r=r*10+p-48; p=getchar(); } return r*f; } void add(int u,int v) { cnt++; e[cnt].ne=h[u]; e[cnt].to=v; h[u]=cnt; } void tarjan(int u) { low[u]=dfn[u]=++tot; v[s[++top]=u]=1; for(int i=h[u];i;i=e[i].ne) { if(!dfn[e[i].to]) { tarjan(e[i].to); low[u]=min(low[u],low[e[i].to]); } else if(v[e[i].to]) low[u]=min(low[u],dfn[e[i].to]); } if(low[u]==dfn[u]) { col++; while(s[top]!=u) { bl[s[top]]=col; va[col]+=a[s[top]]; v[s[top--]]=0; } bl[s[top]]=col; va[col]+=a[s[top]]; v[s[top--]]=0; } } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { x[i]=read(),y[i]=read(); add(x[i],y[i]); } for(int i=1;i<=n;i++) a[i]=read(); st=read(),p=read(); for(int i=1;i<=p;i++) b[i]=read(); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); memset(v,0,sizeof(v)); memset(h,0,sizeof(h)); cnt=0; for(int i=1;i<=m;i++) if(bl[x[i]]!=bl[y[i]]) add(bl[x[i]],bl[y[i]]); for(int i=1;i<=n;i++) dis[i]=-inf; deque<int>q; q.push_back(bl[st]); v[bl[st]]=1; dis[bl[st]]=va[bl[st]]; while(!q.empty()) { int u=q.front(); q.pop_front(); v[u]=0; for(int i=h[u];i;i=e[i].ne) if(dis[e[i].to]<dis[u]+va[e[i].to]) { dis[e[i].to]=dis[u]+va[e[i].to]; if(!v[e[i].to]) { v[e[i].to]=1; if(q.empty()||dis[q.front()]<dis[e[i].to]) q.push_back(e[i].to); else q.push_front(e[i].to); } } } for(int i=1;i<=p;i++) if(dis[bl[b[i]]]>ans) ans=dis[bl[b[i]]]; printf("%d\n",ans); return 0; }
bzoj 1179: [Apio2009]Atm【tarjan+spfa】
标签：
原文地点：https://www.cnblogs.com/lokiii/p/8794622.html