可以发现最后由 (n) 个点组成的图是有环的，我们继而进行缩点后 DP
step 1: 建图
暴力是 (mathcal{O}(n^2)) 的，优化
可以发现同一行的标号均为 1 的点可以形成环
同一列的标号均为 2 的点可以形成环
有以下思路:
先将行数排序作为第一关键字，将是否标号为 1 作为第二关键字对于点排序
取第每一行一个点作为链表头，链上有这一行上标号为 1 的点，最后将链头和链尾相接，就成功得到了一个环
对于这一行上标号不为 1 的点，直接上一条链头到该点的边即可
对于标号为 2 和列的处理与对于行的处理相似
对于标号为 3 的点，考虑暴力加边，可使用std::map或 Hash 优化
step 2: 缩点 & 建 DAG
点权即为环上点的数量，其他都是板子
step 3: 拓扑排序 + DP
(num_v) 为点权
[f_v = max_{(u,v)in DAG} f_u + num_v
]
答案 (Ans = max f_i)
总复杂度 (mathcal{O}(nlog n))
Code(C++):
#include<bits/stdc++.h>
#define forn(i,s,t) for(int i=(s);i<=(t);++i)
using namespace std;
typedef long long LL;
const int N = 1e5+3,Mod = 1e6+7;
const int dxx[] = {1,1,1,-1,-1,-1,0,0};
const int dyy[] = {0,1,-1,1,0,-1,1,-1};
struct List {
int dir,nxt;
}E[N<<3],DAG[N<<3];
int G[N],cnt,G1[N],cnt1,ind[N];
inline void Add(int u,int v) {
E[++cnt].dir = v,E[cnt].nxt = G[u],G[u] = cnt;
}
inline void AddDAG(int u,int v) {
DAG[++cnt1].dir = v,DAG[cnt1].nxt = G1[u],G1[u] = cnt1,ind[v]++;
}
int n,R,C,id[N],x[N],y[N],t[N];
struct Hash { // 乱搞Hash
LL val[N<<2];
int nxt[N<<2],id[N<<2],head[Mod+2],cnt;
inline void Add(int x,int y,int nd) {
LL A = 1ll*(x-1)*C+y;
LL B = A%Mod;
val[++cnt] = A,id[cnt] = nd,nxt[cnt] = head[B];
head[B] = cnt;
}
inline int Fnd(int x,int y) {
LL A = (1ll*(x-1)*C+y) %Mod;
LL B = 1ll*(x-1)*C+y;
for(int i=head[A];i;i=nxt[i])
if(val[i] == B) return id[i];
return -1;
}
}H;
int dfn[N],ord,stk[N],h,clr[N],col,num[N],f[N],Ans;
bool vis[N];
int tarjan(int u) {
int low = dfn[u] = ++ord;
stk[++h] = u,vis[u] = 1;
for(int i=G[u];i;i=E[i].nxt) {
int v = E[i].dir;
if(!dfn[v]) low = min(tarjan(v),low);
else if(vis[v]) low = min(low,dfn[v]);
}
if(low == dfn[u]) {
++col;
do num[col]++,vis[stk[h]]=0,clr[stk[h]]=col;
while(stk[h--]!=u);
}
return low;
}
queue<int> q;
inline bool cmp(int A,int B) {return x[A]!=x[B]?(x[A]<x[B]):((t[A]==1)?1:(!t[B]));}
inline bool cmp1(int A,int B){return y[A]!=y[B]?(y[A]<y[B]):((t[A]==2)?1:(!t[B]));}
int main() {
scanf("%d%d%d",&n,&R,&C);
forn(i,1,n) scanf("%d%d%d",&x[i],&y[i],&t[i]);
forn(i,1,n) H.Add(x[i],y[i],i);
/*--------建图 part----------*/
forn(i,1,n) id[i] = i;
sort(id+1,id+n+1,cmp);
forn(i,1,n) if(t[id[i]] == 1) { // situation 1
int llst=i,lst=id[i],fir=id[i];
for(int j=i+1;j<=n;++j) {
if(x[id[j]]!=x[id[i]]) break ;
llst = j;
if(t[id[j]] == 1) Add(lst,id[j]),lst = id[j];
else Add(id[i],id[j]);
}
if(lst^fir) Add(lst,fir);
i = llst;
}
sort(id+1,id+n+1,cmp1);
forn(i,1,n) if(t[id[i]] == 2) { // situation 2
int llst = i,lst=id[i],fir=id[i];
for(int j=i+1;j<=n;++j) {
if(y[id[i]]!=y[id[j]]) break ;
llst = j;
if(t[id[j]] == 2) Add(lst,id[j]),lst = id[j];
else Add(id[i],id[j]);
}
if(lst^fir) Add(lst,fir);
i = llst;
}
int v;
forn(i,1,n) if(t[i] == 3) // situation 3
forn(j,0,7) if((v=H.Fnd(x[i]+dxx[j],y[i]+dyy[j])) != -1)
Add(i,v);
/*--------缩点 Part--------*/
forn(i,1,n) if(!dfn[i]) tarjan(i);
forn(u,1,n) for(int i=G[u];i;i=E[i].nxt) {
v = E[i].dir;
if(clr[v] == clr[u]) continue ;
AddDAG(clr[u],clr[v]);
}
/*---------DP Part-------*/
forn(i,1,col) if(!ind[i]) q.push(i),f[i] = num[i];
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i=G1[u];i;i=DAG[i].nxt) {
v = DAG[i].dir;
f[v] = max(f[v],f[u]+num[v]);
if(!--ind[v]) q.push(v);
}
}
forn(i,1,col) Ans = max(Ans,f[i]);
printf("%d
",Ans);
return 0;
}