[APIO2009]抢掠计划

洛咕

题意:Siruseri 城中的道路都是单向的。\(M\)条道路由\(N(N,M<=500000)\)个路口连接。按照法律的规定， 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆 祝他的胜利。使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希 望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可 以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机 里面就不会再有钱了.求Banditji最多能抢劫到多少钱?

分析:tarjan缩点后,整个图变成了一个有向无环图,我们从起点所在的强连通分量开始跑spfa最长路即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=500005;
int n,m,sum,s,ans;
int a[N],b[N],ed[N],val[N],visit[N],dis[N];
int tot,head[N],nxt[N],to[N];
int top,num,timeclock;
int size[N],st[N],dfn[N],low[N],color[N];
inline void add(int a,int b){
    nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u){
    dfn[u]=low[u]=++timeclock;
    st[++top]=u;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!color[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        color[u]=++num;
        size[num]+=val[u];
        while(st[top]!=u){
            color[st[top]]=num;
            size[num]+=val[st[top]];
            --top;
        }
        --top;
    }
}
queue<int>q;
inline void spfa(){
    q.push(color[s]);dis[color[s]]=size[color[s]];
    visit[color[s]]=1;
    while(q.size()){
        int u=q.front();q.pop();visit[u]=0;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(dis[v]<dis[u]+size[v]){
                dis[v]=dis[u]+size[v];
                if(!visit[v]){
                    q.push(v);
                    visit[v]=1;
                }
            }
        }
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;++i){
        a[i]=read();b[i]=read();
        add(a[i],b[i]);
    }
    for(int i=1;i<=n;++i)val[i]=read();
    s=read();sum=read();
    for(int i=1;i<=sum;++i)ed[i]=read();
    for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);//缩点
    memset(head,0,sizeof(head));tot=0;
    for(int i=1;i<=m;++i)//重新建图,一个有向无环图
        if(color[a[i]]!=color[b[i]]){
            add(color[a[i]],color[b[i]]);
        }
    spfa();//跑最长路
    for(int i=1;i<=sum;++i)ans=max(ans,dis[color[ed[i]]]);
    printf("%d\n",ans);
    return 0;
}

[APIO2009]抢掠计划

原文：https://www.cnblogs.com/PPXppx/p/11392308.html