【BZOJ1179】【APIO2009】Atm（tarjan+spfa）

Description

Input

第一行包含兩個整數N、M。N表示路口的個數，M表示道路條數。接下來M行，每行兩個整數，這兩個整數都在1到N之間，第i+1行的兩個整數表示第i條道路的起點和終點的路口編号。接下來N行，每行一個整數，按順序表示每個路口處的ATM機中的錢數。接下來一行包含兩個整數S、P，S表示市中心的編号，也就是出發的路口。P表示酒吧數目。接下來的一行中有P個整數，表示P個有酒吧的路口的編号。

Output

輸出一個整數，表示Banditji從市中心開始到某個酒吧結束所能搶劫的最多的現金總數。

Sample Input

6 7

1 2

2 3

3 5

2 4

4 1

2 6

6 5

10

12

8

16

1 5

1 4

4

3

5

6

Sample Output

47

HINT

50%的輸入保證N, M<=3000。所有的輸入保證N, M<=500000。每個ATM機中可取的錢數為一個非負整數且不超過4000。輸入資料保證你可以從市中心沿着Siruseri的單向的道路到達其中的至少一個酒吧。

題解：

這道還好。就是把環縮點，跑最長路即可。因為有多個終點，是以有兩種處理方法：逐個終點比較，或設一個虛拟終點T2。

代碼如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<math.h>
#define ll long long
#define inf 0x7f7f7f7f
#define N 500005
using namespace std;
int n,m,s,p; 
int e[N],nex[N],hd[N],e2[N],nex2[N],hd2[N],tot;
int dfn[N],low[N],tim,q[N],top,scc;
bool inq[N];
int bl[N],v[N],c[N];
int f[N];
void ins(int u,int v){e[++tot]=v,nex[tot]=hd[u],hd[u]=tot;}
void ins2(int u,int v){e2[++tot]=v,nex2[tot]=hd2[u],hd2[u]=tot;}
void tarjan(int x)
{
    int now=;
    dfn[x]=low[x]=++tim;
    q[++top]=x,inq[x]=;
    for(int i=hd[x];i;i=nex[i])
    {
        if(!dfn[e[i]]) 
        {
            tarjan(e[i]);
            low[x]=min(low[x],low[e[i]]);
        }
        else if(inq[e[i]]) low[x]=min(low[x],dfn[e[i]]);
    }
    if(low[x]==dfn[x])
    {
        scc++;
        while(now!=x)
        {
            now=q[top];top--;bl[now]=scc;
            v[scc]+=c[now];
            inq[now]=;
        }
    }
}
void reb()
{
    tot=;
    for(int i=;i<=n;i++)
    for(int j=hd[i];j;j=nex[j])
    if(bl[i]!=bl[e[j]]) ins2(bl[i],bl[e[j]]);
}
void spfa()
{
    queue<int> Q;
    memset(inq,,sizeof(inq));
    Q.push(bl[s]);inq[bl[s]]=;f[bl[s]]=v[bl[s]];
    while(!Q.empty())
    {
        int now=Q.front();Q.pop();
        for(int i=hd2[now];i;i=nex2[i])
        {
            if(f[e2[i]]<f[now]+v[e2[i]])
            {
                f[e2[i]]=f[now]+v[e2[i]];
                if(!inq[e2[i]])
                {
                    inq[e2[i]]=;
                    Q.push(e2[i]);
                }
            }
        }
        inq[now]=;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=,u,v;i<=m;i++) scanf("%d%d",&u,&v),ins(u,v);
    for(int i=;i<=n;i++) scanf("%d",&c[i]);
    for(int i=;i<=n;i++) 
    if(!dfn[i]) tarjan(i);
    scanf("%d%d",&s,&p);
    reb();
    spfa();
    int ans=;
    for(int i=,x;i<=p;i++)
    {
        scanf("%d",&x);
        if(f[bl[x]]>ans) ans=f[bl[x]];  
    }
    printf("%d\n",ans);
    return ;
}