~~~~~      P2403 [SDOI2010] 所驼门王的宝藏 ~~~~~      总题单链接

讲解

~~~~~      这道题的关键在于如何连边。

~~~~~      对于“横天门”和“纵寰门”建虚点即可。

~~~~~      对于“任意门”，用一个 vector 存每行有哪些点，然后二分。

~~~~~      连完边之后缩点，然后 $DP$。

~~~~~      $cnt：$连通块的数量
~~~~~      $dp[i]：$ 到第 $i$ 个连通块最多经过了多少给宝物。

for(ll u=cnt;u>=1;u--){dp[u]+=siz[u];for(ll v:ng[u])dp[v]=max(dp[v],dp[u]);
}

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;ll Q,n,m,dp[3000005];
ll X[3000005],Y[3000005],T[3000005];
vector<ll>han[1000005],eg[3000005],ng[3000000];ll stk[3000005],ins[3000005],top;
ll dfn[3000005],low[3000005],tot;
ll pos[3000005],siz[3000005],cnt;void Tarjan(ll p){dfn[p]=low[p]=++tot;stk[++top]=p;ins[p]=1;for(ll v:eg[p]){if(!dfn[v]){Tarjan(v);low[p]=min(low[p],low[v]);}else if(ins[v])low[p]=min(low[p],dfn[v]);}if(dfn[p]==low[p]){cnt++;while(top){ll v=stk[top--];ins[v]=0;pos[v]=cnt;if(v<=Q)siz[cnt]++;if(v==p)break;}}
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>Q>>n>>m;for(ll i=1;i<=Q;i++){cin>>X[i]>>Y[i]>>T[i];han[X[i]].push_back(i);eg[X[i]+Q].push_back(i);eg[Y[i]+Q+n].push_back(i);if(T[i]==1)eg[i].push_back(X[i]+Q);if(T[i]==2)eg[i].push_back(Y[i]+Q+n);}for(ll i=1;i<=n;i++){if(han[i].empty())continue;sort(han[i].begin(),han[i].end(),[&](ll a,ll b){return Y[a]<Y[b];});}for(ll i=1;i<=Q;i++){if(T[i]!=3)continue;ll U=max(1ll,X[i]-1),D=min(n,X[i]+1);ll L=max(1ll,Y[i]-1),R=min(m,Y[i]+1);for(ll x=U;x<=D;x++){if(han[x].empty())continue;if(Y[han[x][0]]>R)continue;if(Y[han[x][han[x].size()-1]]<L)continue;ll l=0,r=han[x].size()-1,res=0;while(l<=r){ll mid=(l+r)>>1;if(Y[han[x][mid]]>=L)res=mid,r=mid-1;else l=mid+1;}for(ll y=res;y<han[x].size()&&Y[han[x][y]]<=R;y++){if(i==han[x][y])continue;eg[i].push_back(han[x][y]);}}}for(ll i=1;i<=Q+n+m;i++)if(!dfn[i])Tarjan(i);for(ll u=1;u<=Q+n+m;u++)for(ll v:eg[u])if(pos[u]!=pos[v])ng[pos[u]].push_back(pos[v]);for(ll u=cnt;u>=1;u--){dp[u]+=siz[u];for(ll v:ng[u])dp[v]=max(dp[v],dp[u]);}ll ans=0;for(ll i=1;i<=cnt;i++)ans=max(ans,dp[i]);cout<<ans;return 0;
}