[文章目录]
Description
N, M<=500000
tarjan缩点+spfa求最长路。
发现缩点之后图变成了一个拓扑图。（并不是树！！！）然后，答案就变成了求一个合法的强连通分量使得到s路径上点权和最大。spfa求最长路
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501000
int n,m,s,p,ans,fna;
int dfn[N],low[N],bel[N],z[N],top,tot;
bool inz[N],v[N];
int w[N];
int head[N<<1],to[N<<1],nxt[N<<1],f[N],cnt;
inline void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
z[++top]=x; inz[x]=1;
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(inz[to[i]]) low[x]=min(low[x],dfn[to[i]]);
}
if(low[x]==dfn[x])
{
ans++;int t;
do
{
t=z[top--];
inz[t]=0;
bel[t]=ans;
}while(t!=x);
}
}
int dis[N<<1];
bool vis[N<<1];
void spfa(int x)
{
queue<int>q;
memset(dis,0xef,sizeof dis);
dis[x]=0; q.push(x); vis[x]=1;
while(!q.empty())
{
x=q.front(); q.pop(); vis[x]=0;
for(int i=head[x];i;i=nxt[i])
if(dis[to[i]]<dis[x]+f[to[i]-n])
{
dis[to[i]]=dis[x]+f[to[i]-n];
if(!v[to[i]]) q.push(to[i]),vis[to[i]]=1;
}
}
}
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);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
f[bel[i]]+=x;
}
scanf("%d%d",&s,&p);
for(int i=1;i<=p;i++)
{
scanf("%d",&x);
v[bel[x]]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=head[i];j;j=nxt[j])
if(bel[i]!=bel[to[j]])
add(bel[i]+n,bel[to[j]]+n);
}
spfa(bel[s]+n);
for(int i=1;i<=ans;i++)
if(v[i]) fna=max(fna,dis[i+n]);
printf("%d",fna+f[bel[s]]);
return 0;
}