題意：
給定N個(gè)點(diǎn) 有些節(jié)點(diǎn)可以通往同行 有些可以通往同列中的點(diǎn) 有些可以通往八連通的點(diǎn) 可以走過(guò)多次
問(wèn)最多一次可以走過(guò)多少點(diǎn)
做法：
可以走過(guò)多次也就是說(shuō)跟apio2009 atm一樣 一個(gè)強(qiáng)連通分量?jī)?nèi)可以無(wú)限走
然后就是走過(guò)場(chǎng) 縮點(diǎn) 拓?fù)渑判?dp
問(wèn)題在于。。。離散化后每次要尋找(x,y)這個(gè)點(diǎn)是否存在 然后我的二分查找就因?yàn)樾∮诖笥谔?hào)的問(wèn)題掛了。。
（跟cqtsc2010 內(nèi)部白點(diǎn)一樣。。。掛在二分上了！！！）
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