[APIO 2009 ATM]强连通分量、拓扑排序、手写栈、动态规划

【算法分析】

很简单，属于送分题类型。。。

缩点然后topsort+dp就可以了~

但是比较纠结的是会爆栈。。。。比赛不知道会不会的？听说Linux的栈比较大吧。。。

【CODE】

#include #include #include const int N=501111;
const int INF=1000000000;
struct gtp{int x,y,next;}g[N];
int n,e,tot,S,head,tail,ans,stack;
int ls[N],fa[N],color[N],dep[N],list[N],du[N],w[N],F[N],v[N],edge[N],p[N];
bool ed[N];

inline void addedge(int x,int y){
     e++;
     g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

void input(){
     int m,x,y;
     scanf("%d%d",&n,&m);
     for (int i=1;i<=m;i++){
         scanf("%d%d",&x,&y);
         addedge(x,y);
     }
     for (int i=1;i<=n;i++) scanf("%d",&w[i]);
     int num;
     scanf("%d%d",&S,&num);
     for (int i=1;i<=num;i++){
         scanf("%d",&x);
         ed[x]=true;
     }
}

int gf(int k){
    if (fa[k]==k) return k;
    fa[k]=gf(fa[k]);
    return fa[k];
}

void dfs(int k){
/*    
     for (int t=ls[k];t;t=g[t].next)
       if (!dep[g[t].y]){
         dep[g[t].y]=dep[k]+1;
         dfs(g[t].y);
         if (dep[gf(g[t].y)]       }else
       if (!color[gf(g[t].y)] && dep[gf(g[t].y)]         fa[k]=fa[g[t].y];
     color[k]=1;
*/
     stack=1; p[1]=k; edge[1]=ls[k];
     while (stack){
           int &t=edge[stack];
           if (!t){
             color[p[stack]]=1;
             stack–;
             continue;
           }
           if (!dep[g[t].y]){
             dep[g[t].y]=dep[g[t].x]+1;
             stack++;
             p[stack]=g[t].y;
             edge[stack]=ls[g[t].y];
           }else
           if (!color[gf(g[t].y)] && dep[gf(g[t].y)]             fa[g[t].x]=fa[g[t].y];
             edge[stack]=g[edge[stack]].next;
           }else edge[stack]=g[edge[stack]].next;
     }
}

void tarjan(){
     for (int i=1;i<=n;i++){
         fa[i]=i;
         color[i]=0;
         dep[i]=0;
     }
     for (int i=1;i<=n;i++)
       if (!dep[i]){
         dep[i]=1;
         dfs(i);
       }
     for (int i=1;i<=n;i++){
         gf(i);
         if (fa[i]!=i){
           w[fa[i]]+=w[i];
           if (ed[i]) ed[fa[i]]=true;
         }
     }
}

void changegraph(){
     int te=e;
     e=0; memset(ls,0,sizeof(ls));
     for (int i=1;i<=te;i++)
       if (fa[g[i].x]!=fa[g[i].y])
         addedge(fa[g[i].x],fa[g[i].y]);
}

void topsort(){
     memset(du,0,sizeof(du));
     head=0; tail=0;
     for (int i=1;i<=e;i++) du[g[i].y]++;
     for (int i=1;i<=n;i++)
       if (fa[i]==i && !du[i]) list[++tail]=i;
     while (head           head++;
           for (int t=ls[list[head]];t;t=g[t].next){
             du[g[t].y]–;
             if (!du[g[t].y]) list[++tail]=g[t].y;
           }
     }
}

void dp(){
     memset(v,0,sizeof(v));
     for (int i=1;i<=n;i++) F[i]=-INF;
     ans=0;
     head=1;
     while (list[head]!=fa[S]) head++;
     F[fa[S]]=0;
     for (int k=head;k<=tail;k++){
       int &i=list[k];
       if (F[i]==-INF) continue;
       F[i]+=w[i];
       for (int t=ls[i];t;t=g[t].next)
         if (v[g[t].y]!=i){
           v[g[t].y]=i;
           if (F[i]>F[g[t].y]) F[g[t].y]=F[i];
         }
       if (ed[i] && F[i]>ans) ans=F[i];
     }   
     printf("%dn",ans);
}

int main(){
    freopen("atm.in","r",stdin);
    freopen("atm.out","w",stdout);
    input();
    tarjan();
    changegraph();
    topsort();
    dp();
}