洛谷3627 [APIO2009]抢掠计划

题目描述

输入格式：

第一行包含两个整数 N、M。N 表示路口的个数，M 表示道路条数。接下来 M 行，每行两个整数，这两个整数都在 1 到 N 之间，第 i+1 行的两个整数表示第 i 条道路的起点和终点的路口编号。接下来 N 行，每行一个整数，按顺序表示每 个路口处的 ATM 机中的钱数。接下来一行包含两个整数 S、P，S 表示市中心的 编号，也就是出发的路口。P 表示酒吧数目。接下来的一行中有 P 个整数，表示 P 个有酒吧的路口的编号。

输出格式：

输出一个整数，表示 Banditji 从市中心开始到某个酒吧结束所能抢劫的最多 的现金总数。

缩点之后跑spfa，原来我脑残跑最短路挑错挑了半天

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#define maxn 500005

using namespace std;

int dfn[maxn],low[maxn],stk[maxn],bel[maxn];

int n,m,cnt,ind,top,tot;

int head[maxn],dis[maxn],w1[maxn],w2[maxn],x[maxn],y[maxn];

bool vis[maxn],inq[maxn],ok1[maxn],ok2[maxn];

struct edge{

    int next,to,w;

}e[maxn];

void insert(int u,int v,int w){

    cnt++;

    e[cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;

    head[u]=cnt;

}

void tarjan(int x){

    stk[++top]=x;

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

    inq[x]=;

    for(int i=head[x];i;i=e[i].next){

        int s=e[i].to;

        if(!dfn[s]){

            tarjan(s);

            low[x]=min(low[x],low[s]);

        }

        else if(inq[s]){

            low[x]=min(low[x],dfn[s]);

        }

    }

    int now=;

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

        tot++;

        while(now!=x){

            now=stk[top];top--;

            bel[now]=tot;

            inq[now]=;

            w2[tot]+=w1[now];

            if(ok1[now]){

                ok2[tot]=;

            }

        }

    }

}

void spfa(int x){

    queue<int>q;

    memset(dis,0xef,sizeof dis);

    memset(vis,,sizeof vis);

    q.push(x);

    vis[x]=;dis[x]=w2[x];

    while(!q.empty()){

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

    for(int i=head[now];i;i=e[i].next){

        int s=e[i].to;

        if(dis[s]<dis[now]+e[i].w){

            dis[s]=dis[now]+e[i].w;

            if(!vis[s]){

                vis[s]=;

                q.push(s);

                }

            }

        }

    }

}

int main(){

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

    for(int i=;i<=m;i++){

        scanf("%d%d",&x[i],&y[i]);

        insert(x[i],y[i],);

    }

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

        scanf("%d",&w1[i]);

    }

    int u,p,v;

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

    for(int i=;i<=p;i++){

        scanf("%d",&v);

        ok1[v]=;

    }

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

    cnt=;

    memset(head,,sizeof head);

    memset(e,,sizeof e);

    for(int i=;i<=m;i++){

        if(bel[x[i]]!=bel[y[i]])insert(bel[x[i]],bel[y[i]],w2[bel[y[i]]]);

    }

    spfa(bel[u]);

    int ans=;

    for(int i=;i<=tot;i++){

        if(ok2[i]){

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

        }

    }

    printf("%d",ans);

    return ;

}