BZOJ1924 [Sdoi2010]所驼门王的宝藏 【建图 + tarjan】

题目

输入格式

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

输出格式

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

输入样例

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

输出样例

9

提示

题解

把图建出来后就是tarjan + dp了

建图比较烦
我们将其按x排序，先将横向边建上，当一排存在多个横向边时，它们之间两两连边，过于费空间，只连一个环就好了
竖向边也是一样的
最后是第三种边，排个序二分查找就好了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 100005,maxm = 1000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int n,N,M;
int x[maxn],y[maxn],id[maxn],t[maxn];
inline bool cmp1(const int& a,const int& b){
return x[a] == x[b] ? t[a] < t[b] : x[a] < x[b];
}
inline bool cmp2(const int& a,const int& b){
return y[a] == y[b] ? t[a] < t[b] : y[a] < y[b];
}
inline bool cmp3(const int& a,const int& b){
return x[a] == x[b] ? y[a] < y[b] : x[a] < x[b];
}
int h[maxn],ne = 2,h2[maxn],ne2 = 2;
struct EDGE{int to,nxt;}ed[maxm],e[maxm];
inline void build(int u,int v){
    ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;
//printf("build (%d) to (%d)\n",u,v);
}
inline void add(int u,int v){
    e[ne2] = (EDGE){v,h2[u]}; h2[u] = ne2++;
}
inline bool check(const int& p,const int& X,const int& Y){
return x[id[p]] == X ? y[id[p]] >= Y : x[id[p]] > X;
}
int lowb(int X,int Y){
int l = 1,r = n,mid;
while (l < r){
        mid = l + r >> 1;
if (check(mid,X,Y)) r = mid;
else l = mid + 1;
    }
return l;
}
int st[maxn],top;
void Build(){
    sort(id + 1,id + 1 + n,cmp1);
for (int i = 1; i <= n; i++){
int u = i; top = 0;
while (u <= n){
if (x[id[u]] != x[id[i]]) break;
if (t[id[u]] == 1) st[++top] = id[u];
            u++;
        }
if (!top) continue;
if (top > 1){
for (int j = 1; j < top; j++) build(st[j],st[j + 1]);
            build(st[top],st[1]);
        }
for (int j = i; j < u; j++) if (t[id[j]] != 1) build(st[1],id[j]);
        i = --u;
    }
    sort(id + 1,id + 1 + n,cmp2);
for (int i = 1; i <= n; i++){
int u = i; top = 0;
while (u <= n){
if (y[id[u]] != y[id[i]]) break;
if (t[id[u]] == 2) st[++top] = id[u];
            u++;
        }
if (!top) continue;
if (top > 1){
for (int j = 1; j < top; j++) build(st[j],st[j + 1]);
            build(st[top],st[1]);
        }
for (int j = i; j < u; j++) if (t[id[j]] != 2) build(st[1],id[j]);
        i = --u;
    }
    sort(id + 1,id + 1 + n,cmp3);
for (int i = 1; i <= n; i++){
if (t[id[i]] != 3) continue;
int u = lowb(x[id[i]] - 1,y[id[i]] - 1);
for (int j = u; j <= n && x[id[j]] + 1 == x[id[i]] && y[id[j]] >= y[id[i]] - 1 && y[id[j]] <= y[id[i]] + 1; j++)
            build(id[i],id[j]);
        u = lowb(x[id[i]],y[id[i]] - 1);
for (int j = u; j <= n && x[id[j]] == x[id[i]] && y[id[j]] >= y[id[i]] - 1 && y[id[j]] <= y[id[i]] + 1; j++)
if (id[i] != id[j]) build(id[i],id[j]);
        u = lowb(x[id[i]] + 1,y[id[i]] - 1);
for (int j = u; j <= n && x[id[j]] - 1 == x[id[i]] && y[id[j]] >= y[id[i]] - 1 && y[id[j]] <= y[id[i]] + 1; j++)
            build(id[i],id[j]);
    }
}
int dfn[maxn],low[maxn],Scc[maxn],scci,cnt,val[maxn];
void dfs(int u){
    dfn[u] = low[u] = ++cnt;
    st[++top] = u;
    Redge(u){
if (!dfn[to = ed[k].to]){
            dfs(to);
            low[u] = min(low[u],low[to]);
        }else if (!Scc[to]) low[u] = min(low[u],dfn[to]);
    }
if (dfn[u] == low[u]){
        scci++;
do{
            Scc[st[top]] = scci; val[scci]++;
        }while(st[top--] != u);
    }
}
void tarjan(){
for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i);
}
queue<int> q;
int inde[maxn],f[maxn];
void solve(){
for (int i = 1; i <= n; i++){
int u = Scc[i];
        Redge(i) if (Scc[to = ed[k].to] != u)
            add(u,Scc[to]),inde[Scc[to]]++;
    }
for (int i = 1; i <= scci; i++) if (!inde[i]) q.push(i),f[i] = val[i];
int u,ans = 0;
while (!q.empty()){
        u = q.front(); q.pop();
        ans = max(ans,f[u]);
for (int k = h2[u],to; k; k = e[k].nxt){
            f[to = e[k].to] = max(f[to],f[u] + val[to]);
if (!(--inde[to])) q.push(to);
        }
    }
for (int i = 1; i <= scci; i++)
        ans = max(ans,f[i]);
    printf("%d\n",ans);
}
void readin(){
    n = read(); N = read(); M = read();
for (int i = 1; i <= n; i++)
        x[i] = read(),y[i] = read(),t[i] = read(),id[i] = i;
}
int main(){
    readin();
    Build();
    tarjan();
    solve();
return 0;
}