【Luogu】P3627抢掠计划（缩点最短路）

题目链接在此

   有环当然一定尽量走环，这是搞缩点的人都知道的常识。

   建了新图之后搞点权SPFA跑最长路。枚举每个酒吧选择最大值。

   发现我的博客写的越来越水了

#include<cstdio>
#include<cctype>
#include<cstring>
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

inline long long max(long long a,long long b){    return a>b?a:b;    }
inline long long min(long long a,long long b){    return a<b?a:b;    }

struct Edge{
    int next,to;
};

struct Pic{
    Edge edge[1000010];
    int head[500010],num;
    inline void add(int from,int to){
        edge[++num]=(Edge){head[from],to};
        head[from]=num;
    }
}Old,New;

int que[1000000];
int fsh[1000000];
int f[2000000],h,t=1;
int stack[1000000],top;
int dfn[1000000],low[1000000],ID;
int col[1000000],cnt;
int val[1000000];
bool vis[1000000];
int dis[1000000];
void tarjan(int x){
    vis[x]=1;
    dfn[x]=low[x]=++ID;
    stack[++top]=x;
    for(int i=Old.head[x];i;i=Old.edge[i].next){
        int to=Old.edge[i].to;
        if(!dfn[to]){
            tarjan(to);
            low[x]=min(low[x],low[to]);
        }
        else if(vis[to])    low[x]=min(low[x],dfn[to]);
    }
    if(dfn[x]==low[x]){
        vis[x]=0;
        col[x]=++cnt;
        val[cnt]+=que[x];
        while(stack[top]!=x){
            vis[stack[top]]=0;
            val[cnt]+=que[stack[top]];
            col[stack[top--]]=cnt;
        }
        top--;
    }
}
int ans;
int main(){
    int n=read(),m=read();
    for(int i=1;i<=m;++i){
        int from=read(),to=read();
        Old.add(from,to);
    }
    for(int i=1;i<=n;++i)    que[i]=read();
    int s=read(),p=read();
    for(int i=1;i<=p;++i)     fsh[i]=read();
    for(int i=1;i<=n;++i)
        if(!dfn[i])    tarjan(i);
    for(int i=1;i<=n;++i)
        for(int j=Old.head[i];j;j=Old.edge[j].next){
            int to=Old.edge[j].to;
            if(col[i]!=col[to])    New.add(col[i],col[to]);
        }
    f[1]=col[s];
    memset(vis,0,sizeof(vis));
    dis[col[s]]=val[col[s]];
    while(h<t){
        h++;
        int from=f[h];
        vis[from]=0;
        for(int i=New.head[from];i;i=New.edge[i].next){
            int to=New.edge[i].to;
            if(dis[to]<dis[from]+val[to]){
                dis[to]=dis[from]+val[to];
                if(!vis[to]){
                    vis[to]=1;
                    f[++t]=to;
                }
            }
        }
    }
    for(int i=1;i<=p;++i)    ans=max(ans,dis[col[fsh[i]]]);
    printf("%d",ans);
    return 0;
}