什么神奇马蜂()
by CQWDX @ 2023-07-13 16:51:31
```cpp
sz[co]+=w[top];
```
上面的 top 应为 k。
已 AC .
```cpp
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n,m,ans=-INT_MAX,dfn[1000005],dis[1000005],viss[1000005],s,u[1000005],jb[1000005],v[1000005],p,cnt,w[1000005],hd[1000005],val[1000005],nxt[1000005],to[1000005],low[1000005],d[1000005],vis[1000005],in[1000005],top,tot,sta[1000005],co,scc[1000005],sz[1000005];
queue<int>q;
void add(int u,int v){
to[++cnt]=v;
nxt[cnt]=hd[u];
hd[u]=cnt;
}
void addd(int u,int v,int w){
to[++cnt]=v;
nxt[cnt]=hd[u];
val[cnt]=w;
hd[u]=cnt;
}
void tarjan(int x){
low[x]=dfn[x]=++tot;
sta[++top]=x;
in[x]=1;
for(int i(hd[x]);i;i=nxt[i]){
int u=to[i];
if(!dfn[u]){
tarjan(u);
low[x]=min(low[x],low[u]);
}
else if(in[u])
low[x]=min(low[x],dfn[u]);
}
if(dfn[x]==low[x]){
++co;
while(sta[top]!=x){
int k=sta[top];
scc[k]=co;
sz[co]+=w[k];
in[k]=0;
top--;
}
int k=sta[top];
scc[k]=co;
sz[co]+=w[k];
in[k]=0;
top--;
}
}
void spfa(int x){
memset(dis,128,sizeof(dis));
q.push(scc[x]);
viss[scc[x]]=1,dis[scc[x]]=sz[scc[x]];
while(!q.empty()){
int l=q.front();
q.pop();
viss[l]=0;
for(int i(hd[l]);i;i=nxt[i]){
if(dis[to[i]]<dis[l]+val[i]){
dis[to[i]]=dis[l]+val[i];
if(!viss[to[i]])
q.push(to[i]),viss[to[i]]=1;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i(1),x,y;i<=m;i++)
cin>>x>>y,u[i]=x,v[i]=y,add(x,y);
for(int i(1);i<=n;i++)
cin>>w[i];
cin>>s>>p;
for(int i(1);i<=p;i++)
cin>>jb[i];
for(int i(1);i<=n;i++)
if(!dfn[i])
tarjan(i);
cnt=0;
memset(hd,0,sizeof(hd));
memset(to,0,sizeof(to));
memset(nxt,0,sizeof(nxt));
memset(vis,0,sizeof(vis));
for(int i(1);i<=m;i++)
if(scc[u[i]]!=scc[v[i]])
addd(scc[u[i]],scc[v[i]],sz[scc[v[i]]]);
spfa(s);
for(int i(1);i<=p;i++)
ans=max(ans,dis[scc[jb[i]]]);
cout<<ans;
return 0;
}
by timefinder @ 2023-07-29 18:02:20