注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SDOI2010[所驼门王的宝藏]  

2010-07-25 12:46:49|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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);

}

 

  评论这张
 
阅读(464)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018