bzoj1179 [Apio2009]Atm——缩环最长路

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1179

tarjan 缩环，然后求到有酒吧的点的最长路即可；

但一开始想缩环后用拓扑序求答案，不由分说的秒WA了，不知道为什么...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

int const maxn=5e5+;

int n,m,hd[maxn],ct,deg[maxn],col[maxn],cr,head[maxn],sta[maxn],top;

int st,xt,dfn[maxn],low[maxn],tim,a[maxn],p;

ll val[maxn],ans,dis[maxn];

bool vis[maxn],bar[maxn],b[maxn];

queue<int>q;

struct N{

    int to,nxt;

    N(int t=,int n=):to(t),nxt(n) {}

}ed[maxn],edge[maxn];

void tarjan(int x)

{

    dfn[x]=low[x]=++tim;

    vis[x]=; sta[++top]=x;

    for(int i=hd[x],u;i;i=ed[i].nxt)

    {

        if(!dfn[u=ed[i].to])tarjan(u),low[x]=min(low[x],low[u]);

        else if(vis[u])low[x]=min(low[x],dfn[u]);

    }

    if(low[x]==dfn[x])

    {

        int y; cr++;

        while((y=sta[top])!=x)

        {

            vis[y]=; col[y]=cr; top--;

            val[cr]+=a[y];

            if(bar[y])b[cr]=;

        }

        vis[x]=; col[x]=cr; top--;

        val[cr]+=a[x]; if(bar[x])b[cr]=;

    }

}

//void topo()

//{

//    memset(vis,0,sizeof vis);

//    for(int i=1;i<=cr;i++)

//        if(!deg[i])q.push(i);

//    while(q.size())

//    {

//        int x=q.front(); q.pop();

//        if(b[x])vis[x]=1;

//        for(int i=head[x],u;i;i=edge[i].nxt)

//        {

//            if(col[st]==(u=edge[i].to)&&vis[x]){ans=max(ans,val[x]); continue;}

//            if(vis[x])vis[u]=1;

//            val[u]+=val[x]; deg[u]--;

//            if(!deg[u])q.push(u);

//        }

//    }

//    ans+=val[col[st]];

//}

void spfa()

{

    memset(vis,,sizeof vis);

    q.push(col[st]); dis[col[st]]=val[col[st]]; vis[col[st]]=;

    while(q.size())

    {

        int x=q.front(); q.pop(); vis[x]=;

        for(int i=head[x],u;i;i=edge[i].nxt)

        {

            if(dis[u=edge[i].to]<dis[x]+val[u])

            {

                dis[u]=dis[x]+val[u];

                if(!vis[u])vis[u]=,q.push(u);

            }

        }

    }

    for(int i=;i<=cr;i++)

        if(b[i])ans=max(ans,dis[i]);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,x,y;i<=m;i++)

    {

        scanf("%d%d",&x,&y);

        ed[++ct]=N(y,hd[x]); hd[x]=ct;

    }

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    scanf("%d%d",&st,&p);

    for(int i=,x;i<=p;i++)scanf("%d",&x),bar[x]=;

    for(int i=;i<=n;i++) if(!dfn[i])tarjan(i);

    for(int i=;i<=n;i++)

        for(int j=hd[i],u;j;j=ed[j].nxt)

            if(col[u=ed[j].to]!=col[i])

            {

                edge[++xt]=N(col[u],head[col[i]]); head[col[i]]=xt;

//                deg[col[i]]++;

            }

//    topo();

    spfa();

    printf("%lld\n",ans);

    return ;

}