[APIO2009]抢掠计划 ($Tarjan$,最长路)

题目链接

Solution

裸题诶...

直接 \(Tarjan\) 缩点+ \(SPFA\) 最长路即可.

不过在洛谷上莫名被卡... RE两个点...

Code

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=2000008;

int read()

{

    char ch=getchar(); int f=1,w=0;

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}

    return f*w;

}

struct sj{int to,next;}a[maxn];

int head[maxn],size;

int dfn[maxn],low[maxn],belong[maxn],cnt;

int top,sta[maxn],n,m,tot;

int bar[maxn],v[maxn],s,t;

int b[maxn],x,y,cc;

int fr[maxn],to[maxn],num                 ;

ll ww[maxn],w[maxn];

void add(int x,int y)

{

     a[++size].to=y;

     a[size].next=head[x];

     head[x]=size;

}

void tarjan(int x)

{

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

    sta[++top]=x;

    v[x]=1;

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

    {

        int tt=a[i].to;

        if(!dfn[tt]){

          tarjan(tt);

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

        }

        else if(v[tt]) low[x]=min(low[x],dfn[tt]);

    }

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

    {

      belong[x]=++cnt;

      v[x]=0;

      do{

        w[cnt]+=ww[sta[top]];

        belong[sta[top]]=cnt;

        v[sta[top]]=0;

      }while(sta[top--]!=x);

    }

}

void init()

{

    n=read(); m=read();

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

      x=read(),y=read(),add(x,y);

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

      ww[i]=read(); s=read();

      cc=read();

      while(cc--)x=read(),bar[x]=1;

}

ll dis[maxn],ans;

void SPFA()

{

     queue<int>q;

     q.push(s);

     dis[s]=w[s]; v[s]=1;

     while(!q.empty())

     {

          int x=q.front(); q.pop();

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

          {

              int tt=a[i].to;

              if(dis[tt]<dis[x]+w[tt])

              {

                    dis[tt]=dis[x]+w[tt];

                    if(!v[tt])

                    q.push(tt),v[tt]=1;

              }

          }

          v[x]=0;

     }

}

int main()

{

    init();

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

    if(!dfn[i])

    tarjan(i);

    for(int x=1;x<=n;x++)

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

    {

        int tt=a[i].to;

        if(belong[tt]!=belong[x])

        fr[++num]=belong[x],to[num]=belong[tt];

    }

    memset(head,0,sizeof(head));

    memset(a,0,sizeof(a));

    memset(v,0,sizeof(v));

    size=0;

    for(int i=1;i<=num;i++) add(fr[i],to[i]);

    s=belong[s];

    SPFA();

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

      if(bar[i])

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

    cout<<ans<<endl;

}