SDOI2010[所驼门王的宝藏]

强连通缩点,然后动态规划。


CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-7-25


DESCRIPTION:


山东2010年省选 所驼门王的宝藏


*/


#include <stdio.h>


 


const int MAXN=100000+2;


const int NEXT=8;


const int MAXE=1000000;


const int MAXV=200000+2;


const int dx[NEXT]={-1,-1,-1, 0, 0, 1, 1, 1};


const int dy[NEXT]={-1, 0, 1,-1, 1,-1, 0, 1};


struct Door{int x,y,type,id;};


typedef struct struct_edge* edge;


struct struct_edge{int v;edge n;};


int N,R,C;


Door door[MAXN];


struct_edge pool[MAXE];


edge top=pool;


edge adj[MAXV];


int time_stamp;


int LOW[MAXN];


int DFN[MAXN];


int stack_top;


int stack[MAXN];


bool instack[MAXN];


int p[MAXN];


int size[MAXN];


int f[MAXN];


bool less_X(Door a,Door b)


{


     return a.x<b.x;


}


bool less_Y(Door a,Door b)


{


     return a.y<b.y;


}


bool less_X_Y(Door a,Door b)


{


     if (a.x==b.x) return a.y<b.y;


     else return a.x<b.x;


}


bool equal(Door a,Door b)


{


     return a.x==b.x&&a.y==b.y;


}


void quick_sort(bool (*less)(Door,Door),int L,int R)


{


     int i=L,j=R;


     Door mid=door[(L+R)>>1],swap;


     while (i<=j)


     {


           while (less(door[i],mid)) i++;


           while (less(mid,door[j])) j–;


           if (i<=j)


           {


              swap=door[i],door[i]=door[j],door[j]=swap;


              i++,j–;


           }


     }


     if (L<j) quick_sort(less,L,j);


     if (i<R) quick_sort(less,i,R);


}


int binary_search(bool (*less)(Door,Door),int L,int R,Door key)


{


    R++;


    while (L+1!=R)


    {


        int mid=(L+R)>>1;


        if (!less(key,door[mid])) L=mid;


        else R=mid;


    }


    return L;


}


void add_edge(int u,int v)


{


     top->v=v,top->n=adj[u],adj[u]=top++;


}


void build_graph()


{


     quick_sort(less_X,1,N);


     for (int u=1,v;u<=N;u=v)


     {


         int p=0;


         for (v=u;door[u].x==door[v].x&&!p;v++)


             if (door[v].type==1) p=door[v].id;


         if (!p) continue;


         for (v=u;door[u].x==door[v].x;v++)


             add_edge(p,door[v].id);


         for (v=u;door[u].x==door[v].x;v++)


             if (door[v].type==1) adj[door[v].id]=adj[p];


     }


     quick_sort(less_Y,1,N);


     for (int u=1,v;u<=N;u=v)


     {


         int p=0;


         for (v=u;door[u].y==door[v].y&&!p;v++)


             if (door[v].type==2) p=door[v].id;


         if (!p) continue;


         for (v=u;door[u].y==door[v].y;v++)


             add_edge(p,door[v].id);


         for (v=u;door[u].y==door[v].y;v++)


             if (door[v].type==2) adj[door[v].id]=adj[p];


     }


     quick_sort(less_X_Y,1,N);


     for (int u=1;u<=N;u++)


         if (door[u].type==3)


         {


            Door key;


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


            {


                key.x=door[u].x+dx[i];


                key.y=door[u].y+dy[i];


                int v=binary_search(less_X_Y,1,N,key);


                if (equal(door[v],key)) add_edge(door[u].id,door[v].id);


            }


         }


}


void tarjan(int u)


{


     instack[stack[++stack_top]=u]=true;


     DFN[u]=LOW[u]=++time_stamp;


     for (edge i=adj[u];i;i=i->n)


         if (!DFN[i->v])


         {


            tarjan(i->v);


            LOW[u]=LOW[i->v]<LOW[u]?LOW[i->v]:LOW[u];


         }


         else if (instack[i->v]) LOW[u]=DFN[i->v]<LOW[u]?DFN[i->v]:LOW[u];


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


     {


        do


        {


          int st=stack[stack_top];


          add_edge(u+N,st);


          size[p[st]=u]++;


          instack[st]=false;


        }


        while (stack[stack_top–]!=u);


     }


}


int dp(int u)


{


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


    else


    {


        for (edge j=adj[u+N];j;j=j->n)


            for (edge i=adj[j->v];i;i=i->n)


                if (p[i->v]!=u)


                   f[u]>?=dp(p[i->v]);


        f[u]+=size[u];


        return f[u];


    }


}


int main()


{


    scanf(“%d%d%d”,&N,&R,&C);


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


        scanf(“%d%d%d”,&door[i].x,&door[i].y,&door[i].type),door[i].id=i;


    build_graph();


    for (int u=1;u<=N;u++)


        if (!DFN[u]) tarjan(u);


    int answer=0;


    for (int u=1;u<=N;u++)


        if (dp(p[u])>answer)


           answer=dp(p[u]);


    printf(“%d\n”,answer);


}