Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

SDTSC 2010 sotomon

题意:
给定N个点 有些节点可以通往同行 有些可以通往同列中的点 有些可以通往八连通的点 可以走过多次
问最多一次可以走过多少点

做法:
可以走过多次也就是说跟apio2009 atm一样 一个强连通分量内可以无限走
然后就是走过场 缩点 拓扑排序 dp

问题在于。。。离散化后每次要寻找(x,y)这个点是否存在  然后我的二分查找就因为小于大于号的问题挂了。。

(跟cqtsc2010 内部白点一样。。。挂在二分上了!!!)

  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 #define n 300005
  5 #define m 3000005
  6 struct Tpnt
  7 {
  8     int x,y,kind,o;
  9 }    T[100005];
 10 int vtx[m],ne[m],L[n],tot,Tot,All,Sub,E;
 11 int N,R,C,dfn[n],F[n],cnt[n],low[n],Stk[n],Deg[n],sub[n],p[n];
 12 int x[100005],y[100005],cnt_x[1000005],place_x[1000005],place_y[1000005];
 13 int X[m],Y[m];
 14 bool vis[n];
 15 inline bool cmp_x(const Tpnt &a,const Tpnt &b)
 16 {
 17     return a.x<b.x||a.x==b.x&&a.y<b.y; 
 18 }
 19 inline bool cmp_y(const Tpnt &a,const Tpnt &b)
 20 {
 21     return a.y<b.y||a.y==b.y&&a.x<b.x;
 22 }
 23 inline void Ins(int u,int v)
 24 {
 25     vtx[++tot]=v;ne[tot]=L[u];L[u]=tot;
 26 }
 27 inline int findx_x(int X)
 28 {
 29     int l=0,r=N,mid;
 30     for (;l+1<r;)
 31     if (mid=(l+r)>>1,T[mid].x<X)    l=mid;
 32     else    r=mid;
 33     if (T[r].x==X)    return r;
 34     return -1;
 35 }
 36 inline int findx_y(int st,int en,int Y)
 37 {
 38     int l=st-1,r=en,mid;
 39     for (;l+1<r;)
 40     if (mid=(l+r)>>1,T[mid].y<Y)    l=mid;
 41     else    r=mid;
 42     if (T[r].y==Y)    return r;
 43     return -1;
 44 }
 45 inline void Tarjan(int u)
 46 {
 47     dfn[u]=low[u]=++All;
 48     vis[Stk[++Stk[0]]=u]=1;
 49     for (p[u]=L[u];p[u];p[u]=ne[p[u]])
 50     if (!dfn[vtx[p[u]]])    Tarjan(vtx[p[u]]),low[u]=min(low[u],low[vtx[p[u]]]);
 51     else
 52     if (vis[vtx[p[u]]])    low[u]=min(low[u],dfn[vtx[p[u]]]);
 53     if (dfn[u]==low[u])
 54         for (++Sub;;)
 55         {
 56             vis[Stk[Stk[0]]]=0;
 57             sub[Stk[Stk[0]]]=Sub;
 58             if (Stk[Stk[0]--]==u)    break;
 59         }
 60 }
 61 inline void Topo()
 62 {
 63     Stk[0]=0;
 64     for (int i=1;i<=Sub;++i)
 65     if (!Deg[i])    F[i]=cnt[i],Stk[++Stk[0]]=i;
 66     for (;Stk[0];)
 67     {
 68         int u=Stk[Stk[0]--];
 69         for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
 70         {
 71             F[v]=max(F[v],F[u]+cnt[v]);
 72             --Deg[v];
 73             if (!Deg[v])    Stk[++Stk[0]]=v;
 74         }
 75     }
 76 }
 77 int main()
 78 {
 79     scanf("%d%d%d",&N,&R,&C);
 80     for (int i=1;i<=N;++i)
 81         scanf("%d%d%d",&T[i].x,&T[i].y,&T[i].kind),T[i].o=i;
 82     sort(T+1,T+N+1,cmp_x);
 83     E=0;
 84     for (int i=1;i<=N;++i)
 85     {
 86         if (T[i].x!=T[i-1].x)
 87         {
 88             x[++x[0]]=T[i].x;
 89             place_x[T[i].x]=x[0];
 90         }
 91         ++cnt_x[T[i].x];
 92         Ins(x[0]+N,T[i].o);
 93         X[++E]=x[0]+N,Y[E]=T[i].o;
 94     }
 95     sort(T+1,T+N+1,cmp_y);
 96     for (int i=1;i<=N;++i)
 97     {
 98         if (T[i].y!=T[i-1].y)
 99         {
100             y[++y[0]]=T[i].y;
101             place_y[T[i].y]=y[0];
102         }
103         Ins(y[0]+N+x[0],T[i].o);
104         X[++E]=y[0]+N+x[0],Y[E]=T[i].o;
105     }
106     Tot=N+x[0]+y[0];
107     sort(T+1,T+N+1,cmp_x);
108     for (int i=1;i<=N;++i)
109     if (T[i].kind==1)
110     {
111         Ins(T[i].o,place_x[T[i].x]+N);
112         X[++E]=T[i].o,Y[E]=place_x[T[i].x]+N;
113     }
114     else
115     if (T[i].kind==2)
116     {
117         Ins(T[i].o,place_y[T[i].y]+N+x[0]);
118         X[++E]=T[i].o,Y[E]=place_y[T[i].y]+N+x[0];
119     }
120     else
121         for (int dx=-1;dx<=1;++dx)
122         if (T[i].x+dx>0&&T[i].x+dx<=R)
123         {
124             int xst=findx_x(T[i].x+dx),xen;
125             if (xst<0)    continue;
126             xen=xst+cnt_x[T[i].x+dx]-1;
127             for (int dy=-1;dy<=1;++dy)
128             if (T[i].y+dy>0&&T[i].y+dy<=C)
129             {
130                 if (!dx&&!dy)    continue;
131                 int pos=findx_y(xst,xen,T[i].y+dy);
132                 if (pos<0||i==pos)    continue;
133                 Ins(T[i].o,T[pos].o);
134                 X[++E]=T[i].o,Y[E]=T[pos].o;
135             }
136         }
137     for (int i=1;i<=Tot;++i)
138     if (!dfn[i])    Tarjan(i);
139     for (int i=1;i<=N;++i)
140         ++cnt[sub[i]];
141     tot=0;
142     memset(L,0,sizeof(L));
143     for (int i=1;i<=E;++i)
144     if (sub[X[i]]!=sub[Y[i]])
145     {
146         Ins(sub[X[i]],sub[Y[i]]);
147         ++Deg[sub[Y[i]]];
148     }
149     Topo();
150     int ret=0;
151     for (int i=1;i<=Sub;++i)
152         ret=max(ret,F[i]);
153     printf("%d\n",ret);
154     return 0;
155 }
156 


posted on 2010-05-13 17:12 jsn1993 阅读(330) 评论(0)  编辑 收藏 引用 所属分类: Graph Theory && Network Flow


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理