强连通缩点，然后动态规划。
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);
}