【洛谷P3627】[APIO2009]抢掠计划

抢掠计划

题目链接

比较水的缩点模板题，Tarjan缩点，重新建图，记录联通块的钱数、是否有酒吧

DAG上记忆化搜索即可

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define N 500010

 inline int read(){

     int x=; char c=getchar();

     while(c<''||c>'') c=getchar();

     while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

     return x;

 }

 int n,m,s,p,val[N],Val[N];

 int head[N],to[N],next[N],sume;

 bool ins[N],bar[N],Bar[N];

 int dfn[N],low[N],stack[N],top,cnt,num;

 int belong[N],Head[N],To[N],Next[N],Sume;

 int f[N];

 inline void add(int x,int y){

     to[++sume]=y;

     next[sume]=head[x];

     head[x]=sume;

 }

 inline void Add(int x,int y){

     To[++Sume]=y;

     Next[Sume]=Head[x];

     Head[x]=Sume;

 }

 inline void dfs(int t){　　//Tarjan缩点

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

     ins[t]=; stack[++top]=t;

     for(int i=head[t];i;i=next[i]){

         int v=to[i];

         if(!dfn[v]){

             dfs(v);

             low[t]=min(low[t],low[v]);

         }

         else if(ins[v])

             low[t]=min(low[t],dfn[v]);

     }

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

         num++;

         while(stack[top]!=t){

             int k=stack[top];

             belong[k]=num;

             ins[k]=;

             if(bar[k]) Bar[num]=;

             Val[num]+=val[k];

             top--;

         }

         belong[t]=num;

         ins[t]=;

         if(bar[t]) Bar[num]=;

         Val[num]+=val[t];

         top--;

     }

 }

 bool dfs2(int u){　　　　//记忆化搜索

     if(f[u]) return f[u];

     int maxx=; bool flag=Bar[u];

     for(int i=Head[u];i;i=Next[i])

      if(dfs2(To[i])){

          flag=;

          maxx=max(maxx,f[To[i]]);

      }

     if(flag) f[u]=maxx+Val[u];

     else f[u]=;

     return flag;

 }

 int main()

 {

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

     int x,y;

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

         x=read(); y=read();

         add(x,y);

     }

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

      val[i]=read();

     s=read(); p=read();

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

         x=read();

         bar[x]=;

     }

     dfs(s);

     for(int u=;u<=n;u++)　　　　//重新建图

      for(int j=head[u];j;j=next[j]){

          int v=to[j];

          if(belong[u]!=belong[v])

           Add(belong[u],belong[v]);

      }

     dfs2(belong[s]);

     printf("%d",f[belong[s]]);

     return ;

 }