附上代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MaxN=100000,MaxL=1000000;
#define XGATE 1
#define YGATE 2
#define RGATE 3
#define EDGE(u,function)\
{\
if(gate[u].type==XGATE){\
for(int v:xGate[gate[u].x]){function}\
}else if(gate[u].type==YGATE){\
for(int v:yGate[gate[u].y]){function}\
}else if(gate[u].type==RGATE){\
for(int i=0;i<8;i++){\
int vx=gate[u].x+posX[i],vy=gate[u].y+posY[i];\
auto it=palace[vx].find(vy);\
if(it==palace[vx].end())continue;\
int v=it->second;\
{function}\
}\
}\
}
int n,r,c;
struct Gate{
Gate(){}
Gate(const int x,const int y,const int type)
:x(x),y(y),type(type){}
int x,y,type;
}gate[MaxN+1];
unordered_map<int,unordered_map<int,int> >palace;
vector<int>xGate[MaxL+1],yGate[MaxL+1];
int xCnt[MaxL+1],yCnt[MaxL+1];
int posX[]={1,1,1,0,-1,-1,-1,0},posY[]={1,0,-1,-1,-1,0,1,1};
int dfn[MaxN+1],low[MaxN+1],sign=0;
bool inStack[MaxN+1];
int stk[MaxN+1],sTop=0;
int scc=0,bel[MaxN+1],sccSize[MaxN+1];
void Tarjan(const int u){
dfn[u]=low[u]=++sign;
stk[++sTop]=u;
inStack[u]=true;
EDGE(u,{
if(u!=v){
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(inStack[v]){
low[u]=min(low[u],dfn[v]);
}
}
}
);
if(low[u]==dfn[u]){
++scc;
while(stk[sTop]!=u){
bel[stk[sTop]]=scc;
inStack[stk[sTop]]=false;
sccSize[scc]++;
sTop--;
}
bel[u]=scc;
inStack[u]=false;
sccSize[scc]++;
sTop--;
}
}
vector<int>g[MaxN+1];
void MakeGraph(){
for(int u=1;u<=n;u++)EDGE(u,
{
if(bel[u]!=bel[v])
g[bel[u]].push_back(bel[v]);
}
);
}
int rd[MaxN+1],dis[MaxN+1];
void TopSort(){
for(int u=1;u<=scc;u++){
for(int v:g[u]){
rd[v]++;
}
}
queue<int>q;
for(int u=1;u<=scc;u++){
if(!rd[u]){
q.push(u);
dis[u]=sccSize[u];
}
}
while(!q.empty()){
int u=q.front();q.pop();
for(int v:g[u]){
rd[v]--;
dis[v]=max(dis[v],dis[u]+sccSize[v]);
if(!rd[v])q.push(v);
}
}
}
void Solve(){
cin>>n>>r>>c;
for(int i=1;i<=n;i++){
int x,y,t;
cin>>x>>y>>t;
gate[i]=Gate(x,y,t);
palace[x][y]=i;
xCnt[x]++;
xCnt[y]++;
}
for(int i=1;i<=r;i++)xGate[i].reserve(xCnt[i]);
for(int i=1;i<=c;i++)yGate[i].reserve(yCnt[i]);
for(int i=1;i<=n;i++){
xGate[gate[i].x].push_back(i);
yGate[gate[i].y].push_back(i);
}
for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
MakeGraph();
TopSort();
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dis[i]);
cout<<ans;
}
int main(){
// freopen("data.in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
// int T;
// cin>>T;
// while(T--)
Solve();
return 0;
}
```
by Msents @ 2023-08-17 17:06:53
@[Msents](/user/198964) 啥?不用优化建图?
降蓝吧(迫真
虽然觉得就算不加优化建图有也没有紫
by int08 @ 2023-11-01 16:41:07