APIO2009[抢掠计划/atm]

感觉和NOIP2009提高组第3题差不多,要强连通缩点,我用的是Tarjan算法,以前看不懂,现在才理解了。


然后再动态规划。


还有,就是数据很变态,单纯的递归过不了,要将之非递归化。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-18


DESCRIPTION:


$DESCRIPTION


*/


#include <stdio.h>


 


#define MAXN 500000


#define MAXM 500000


#define MIN(a,b) ((a)<(b)?(a):(b))


 


struct Link{Link* next;int to;};


 


int N,M;


Link* link[MAXN];


int money[MAXN];


int S,P;


bool isBar[MAXN];


int belong[MAXN];


 


void insert(int,int);


void tarjan(int);


int DP(int);


 


int main()


{


    //freopen(“atm.in”,”r”,stdin);


    //freopen(“atm.out”,”w”,stdout);


   


    scanf(“%d %d\n”,&N,&M);


    for (int i=0;i<M;i++)


    {


        int u,v;


        scanf(“%d %d\n”,&u,&v);


        insert(u-1,v-1);


    }


    for (int i=0;i<N;i++)


        scanf(“%d\n”,&money[i]);


    scanf(“%d %d\n”,&S,&P);


    for (int i=0;i<P;i++)


    {


        int pos;


        if (i+1!=P) scanf(“%d “,&pos);


        else scanf(“%d\n”,&pos);


        isBar[pos-1]=true;


    }


    /*


    for (int root=0;root<N;root++)


    {


        printf(“%d:”,root+1);


        for (Link* i=link[root];i!=0;i=i->next)


            printf(“%d “,i->to+1);


        printf(“\n”);


    }


    */


    tarjan(S-1);


    /*


    for (int i=0;i<N;i++)


        if (belong[i]==i)


           printf(“%d %d %d\n”,i+1,isBar[i],money[i]);


    */


    printf(“%d\n”,DP(S-1));


    //fclose(stdin);


    //fclose(stdout);


    return 0;


}


 


void insert(int u,int v)


{


     static int pool_counter;


     static Link pool[MAXM*4];


     pool[pool_counter].to=v;


     pool[pool_counter].next=link[u];


     link[u]=&pool[pool_counter++];


}


void tarjan(int start)


{


     static int DFN[MAXN];


     static int LOW[MAXN];


     static int stamp;


     static int stack[MAXN];


     static bool instack[MAXN];


     static int top;


     static bool visited[MAXN];


    


     static int depth;


     static Link* i[MAXN];


     static int root[MAXN];


    


     i[depth]=link[root[depth]=start];


     DFN[root[depth]]=LOW[root[depth]]=++stamp;


     instack[stack[top++]=root[depth]]=true;


     visited[root[depth]]=true;


    


     do


     {


       //printf(“root=%d LOW=%d DFN=%d\n”,root[depth]+1,LOW[root[depth]],DFN[root[depth]]);


       if (i[depth])


       {


          if (!visited[i[depth]->to])


          {


             i[depth+1]=link[root[depth+1]=i[depth]->to];


             DFN[root[depth+1]]=LOW[root[depth+1]]=++stamp;


             instack[stack[top++]=root[depth+1]]=true;


             visited[root[depth+1]]=true;


             i[depth]=i[depth]->next;


             depth++;


          }


          else if (instack[i[depth]->to])


          {


              LOW[root[depth]]=MIN(LOW[root[depth]],DFN[i[depth]->to]);


              i[depth]=i[depth]->next;


          }


          else i[depth]=i[depth]->next;


       }


       else


       {


           if (LOW[root[depth]]==DFN[root[depth]])


           {             


              //printf(“GET:”);


              //do instack[stack[–top]]=false,printf(“%d “,stack[top]+1);


              //while (stack[top]!=root[depth]);


              //printf(“\n”);             


              do


              {


                instack[stack[–top]]=false;


                if (isBar[stack[top]])


                   isBar[root[depth]]=true;


                if (stack[top]!=root[depth])


                   money[root[depth]]+=money[stack[top]];


                belong[stack[top]]=root[depth];


                for (Link* j=link[stack[top]];j!=0;j=j->next)


                    insert(root[depth],j->to);


              }


              while (stack[top]!=root[depth]);


           }


           if (depth>0)


              LOW[root[depth-1]]=MIN(LOW[root[depth-1]],LOW[root[depth]]);


           depth–;


       }


     }


     while (depth>=0);


}


/*BACKUP 1ST VERSION


void tarjan(int root)


{


     static int DFN[MAXN];


     static int LOW[MAXN];


     static int stamp;


     static int stack[MAXN];


     static bool instack[MAXN];


     static int top;


     static bool visited[MAXN];


    


     DFN[root]=LOW[root]=++stamp;


     instack[stack[top++]=root]=true;


     visited[root]=true;


    


     for (Link* i=link[root];i!=0;i=i->next)


         if (!visited[i->to])


         {


            tarjan(i->to);


            LOW[root]=MIN(LOW[root],LOW[i->to]);


         }


         else if (instack[i->to])


              LOW[root]=MIN(LOW[root],DFN[i->to]);


    


     if (LOW[root]==DFN[root])


     {


              do


              {


                instack[stack[–top]]=false;


                if (isBar[stack[top]])


                   isBar[root]=true;


                if (stack[top]!=root)


                   money[root]+=money[stack[top]];


                belong[stack[top]]=root;


                for (Link* j=link[stack[top]];j!=0;j=j->next)


                    insert(root,j->to);


              }


              while (stack[top]!=root);


       


        //printf(“GET:”);


        //do instack[stack[–top]]=false,printf(“%d “,stack[top]+1);


        //while (stack[top]!=root);


        //printf(“\n”);


       


     }


}


*/


int DP(int start)


{


    static bool calced[MAXN];


    static int MAX[MAXN];


    start=belong[start];


    if (!calced[start])


    {


       calced[start]=true;      


       for (Link* i=link[start];i!=0;i=i->next)


           if (MAX[start]<DP(i->to))


                  MAX[start]=DP(i->to);


       if (MAX[start]) MAX[start]+=money[start];


       else if (isBar[start]) MAX[start]=money[start];


    }


    return MAX[start];


}


 

留下评论

电子邮件地址不会被公开。