所驼门王的宝藏（bzoj 1924）

Description

Input

第一行给出三个正整数 N, R, C。以下 N 行，每行给出一扇传送门的信息，包含三个正整数xi, yi, Ti，表示该传送门设在位于第 xi行第yi列的藏宝宫室，类型为 Ti。Ti是一个1~3间的整数， 1表示可以传送到第 xi行任意一列的“横天门”，2表示可以传送到任意一行第 yi列的“纵寰门”，3表示可以传送到周围 8格宫室的“自由门”。保证 1≤xi≤R，1≤yi≤C，所有的传送门位置互不相同。

Output

只有一个正整数，表示你确定的路线所经过不同藏宝宫室的最大数目。

Sample Input

10 7 7
2 2 1
2 4 2
1 7 2
2 7 3
4 2 2
4 4 1
6 7 3
7 7 1
7 5 2
5 2 1

Sample Output

HINT

测试点编号 N R C 1 16 20 20 2 300 1,000 1,000 3 500 100,000 100,000 4 2,500 5,000 5,000 5 50,000 5,000 5,000 6 50,000 1,000,000 1,000,000 7 80,000 1,000,000 1,000,000 8 100,000 1,000,000 1,000,000 9 100,000 1,000,000 1,000,000 10 100,000 1,000,000 1,000,000

/*

    按照题目要求建图，缩点跑最长路。

*/

#include<cstdio>

#include<iostream>

#include<vector>

#include<map>

#define N 100010

#define M 1000010

using namespace std;

int x[N],y[N],t[N],K,n,m;

int head1[N],head2[N],cnt;

int low[N],dfn[N],sta[N],ins[N],bl[N],num[N],indexx,top,scc;

int dep[N],vis[N],ans;

int dx[]={,,,,,-,-,-};

int dy[]={,-,,,-,,,-};

struct node{int v,pre;}e1[M],e2[M];

vector<int> a[M],b[M];

map<int,int> mp[M];

void add1(int u,int v){

    if(u==v) return;

    e1[++cnt].v=v;e1[cnt].pre=head1[u];head1[u]=cnt;

}

void add2(int u,int v){

    e2[++cnt].v=v;e2[cnt].pre=head2[u];head2[u]=cnt;

}

void build(){

    for(int i=;i<=n;i++){

        int x=;

        for(int j=;j<a[i].size();j++)

            if(t[a[i][j]]==) {x=a[i][j];break;}

        for(int j=;j<a[i].size();j++){

            add1(x,a[i][j]);

            if(t[a[i][j]]==) add1(a[i][j],x);

        }

    }

    for(int i=;i<=m;i++){

        int x=;

        for(int j=;j<b[i].size();j++)

            if(t[b[i][j]]==) {x=b[i][j];break;}

        for(int j=;j<b[i].size();j++){

            add1(x,b[i][j]);

            if(t[b[i][j]]==) add1(b[i][j],x);

        }

    }

    for(int i=;i<=K;i++)

        if(t[i]==)

            for(int j=;j<;j++){

                int t=mp[x[i]+dx[j]][y[i]+dy[j]];

                if(t) add1(i,t);

            }

}

void tarjan(int u){

    dfn[u]=low[u]=++indexx;

    sta[++top]=u;ins[u]=;

    for(int i=head1[u];i;i=e1[i].pre)

        if(!dfn[e1[i].v]){

            tarjan(e1[i].v);

            low[u]=min(low[u],low[e1[i].v]);

        }

        else if(ins[e1[i].v])

            low[u]=min(low[u],dfn[e1[i].v]);

    int x;

    if(low[u]==dfn[u]){

        ++scc;

        do {

            x=sta[top--];

            ins[x]=;

            bl[x]=scc;

            num[scc]++;

        }while(u!=x);

    }

}

void rebuild(){

    cnt=;

    for(int i=;i<=K;i++)

        for(int j=head1[i];j;j=e1[j].pre)

            if(bl[i]!=bl[e1[j].v])

                add2(bl[i],bl[e1[j].v]);

}

void dfs(int x){

    vis[x]=;

    for(int i=head2[x];i;i=e2[i].pre){

        if(!vis[e2[i].v]) dfs(e2[i].v);

        dep[x]=max(dep[x],dep[e2[i].v]);

    }

    dep[x]+=num[x];

    ans=max(ans,dep[x]);

}

int main(){

    scanf("%d%d%d",&K,&n,&m);

    for(int i=;i<=K;i++){

        scanf("%d%d%d",&x[i],&y[i],&t[i]);

        mp[x[i]][y[i]]=i;

        a[x[i]].push_back(i);

        b[y[i]].push_back(i);

    }

    build();

    for(int i=;i<=K;i++)

        if(!dfn[i]) tarjan(i);

    rebuild();

    for(int i=;i<=scc;i++)

        if(!vis[i]) dfs(i);

    printf("%d",ans);

    return ;

}

巴特西