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

时间:2021-08-24 05:16:31

题目

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

提示

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

题解

把图建出来后就是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;
}