BZOJ1179 : [Apio2009]Atm 缩点+spfa

1179: [Apio2009]Atm

Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 2069 Solved: 826
[Submit][Status][Discuss]

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

HINT

50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

题解：先对图缩点，再求最大值路径就好了跑tarjan后重建图再跑spfa就可以AC

///

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#include<bitset>

#include<set>

#include<vector>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define meminf(a) memset(a,127,sizeof(a));

#define memfy(a)  memset(a,-1,sizeof(a));

#define TS printf("111111\n");

#define FOR(i,a,b) for( int i=a;i<=b;i++)

#define FORJ(i,a,b) for(int i=a;i>=b;i--)

#define READ(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define mod 1000000007

#define inf 100000000

inline ll read(){ll x=,f=;char ch=getchar();while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}return x*f;}

//****************************************

#define maxn  500000+5

int pub,hav[maxn],s,top,vis[maxn],head[maxn],dist[maxn],belong[maxn],value[maxn],va[maxn],t,inq[maxn],q[maxn],scc,cnt;

int dfn[maxn],n,m,p,low[maxn],hea[maxn];

struct ss

{

    int to,next,u;

}e[maxn*],newe[maxn*];

void init()

{

    mem(head);mem(vis);scc=;mem(hav);mem(hea);

    t=;cnt=;top=;mem(va);mem(dist);

}

void add(int u,int v)

{

    e[t].next=head[u];

    e[t].to=v;

    e[t].u=u;

    head[u]=t++;

}

void addd(int u,int v)

{

    newe[t].to=v;

    newe[t].next=hea[u];

    hea[u]=t++;

}

void dfs(int x)

{

    vis[x]=inq[x]=;

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

    q[++top]=x;

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

    {

        if(!vis[e[i].to])

        {

            dfs(e[i].to);

            low[x]=min(low[x],low[e[i].to]);

        }

        else if(inq[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);

    }

    int v=-;

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

    {

       scc++;

        while(v!=x)

        {

            v=q[top--];

            inq[v]=;

            belong[v]=scc;

            hav[scc]+=value[v];

        }

    }

}

void tarjan()

{

    FOR(i,,n)if(!vis[i])dfs(i);

    t=;mem(hea);

    FOR(i,,n)

    {

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

            if(belong[e[j].to]!=belong[i])

                addd(belong[i],belong[e[j].to]);

        }

    }

}

void spfa()

{

    queue<int >Q;

    Q.push(belong[s]);

    inq[belong[s]]=;

    dist[belong[s]]=hav[belong[s]];

    while(!Q.empty())

    {

      int k=Q.front();

        Q.pop();

       inq[k]=;

        for(int i=hea[k];i;i=newe[i].next)

        {

            if(dist[k]+hav[newe[i].to]>dist[newe[i].to])

            {

                dist[newe[i].to]=dist[k]+hav[newe[i].to];

                if(!inq[newe[i].to])

                {

                    inq[newe[i].to]=;

                     Q.push(newe[i].to);

                }

            }

        }

    }

}

int main()

{

    n=read();

    m=read();

    int a,b;

    init();

    FOR(i,,m)

    {

        scanf("%d%d",&a,&b);

        add(a,b);

    }

    FOR(i,,n)scanf("%d",&value[i]);

    tarjan();

    s=read();

    p=read();

    spfa();

    int ans=-;

    FOR(i,,p)

    {

        scanf("%d",&pub);

        ans=max(ans,dist[belong[pub]]);

    }

    cout<<ans<<endl;

    return ;

}

代码

巴特西