# 洛谷 P2403 [SDOI2010]所驼门王的宝藏 题解

## 代码

```#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int dx[10]={0,0,1,-1,1,1,-1,-1};
int dy[10]={1,-1,0,0,-1,1,-1,1};
struct asd{
int to,next;
}b[maxn];
void ad(int aa,int bb){
b[tot].to=bb;
}
struct jll{
int jlx,jly,jlb,id;
}jl[maxn];
int n,r,c,nx,ny,nb,rd[maxn];
int dfn[maxn],low[maxn],dfnc,sta[maxn],top,js,shuyu[maxn],siz[maxn];
void tar(int xx){
dfn[xx]=low[xx]=++dfnc;
sta[++top]=xx;
int u=b[i].to;
if(!dfn[u]){
tar(u);
low[xx]=min(low[u],low[xx]);
} else if(!shuyu[u]){
low[xx]=min(low[xx],dfn[u]);
}
}
if(dfn[xx]==low[xx]){
js++;
while(1){
int now=sta[top--];
shuyu[now]=js;
siz[js]++;
if(now==xx) break;
}
}
}
map<pair<int,int>,bool> mp;
struct asd2{
int to,next,val;
}b2[maxn];
int h2[maxn],t2=1;
void ad2(int aa,int bb,int cc){
b2[t2].to=bb;
b2[t2].next=h2[aa];
b2[t2].val=cc;
h2[aa]=t2++;
}
int f[maxn],ans=0;
void tp(){
queue<int> q;
q.push(0);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=h2[now];i!=-1;i=b2[i].next){
int u=b2[i].to;
rd[u]--;
f[u]=max(f[u],f[now]+b2[i].val);
if(rd[u]==0) q.push(u);
}
}
}
bool cmplh(jll aa,jll bb){
if(aa.jlb==bb.jlb && aa.jlx==bb.jlx) return aa.jly<bb.jly;
if(aa.jlb==bb.jlb) return aa.jlx<bb.jlx;
return aa.jlb<bb.jlb;
}
bool cmpll(jll aa,jll bb){
if(aa.jlb==bb.jlb && aa.jly==bb.jly) return aa.jlx<bb.jlx;
if(aa.jlb==bb.jlb) return aa.jly<bb.jly;
if(aa.jlb==2) return 1;
return 0;
}
bool cmpry(jll aa,jll bb){
return aa.jlb>bb.jlb;
}
map<pair<int,int>,int> mpp;
int htm[maxn],ztm[maxn];
int main(){
memset(h2,-1,sizeof(h2));
for(int i=1;i<=n;i++){
jl[i].id=i;
mpp[make_pair(jl[i].jlx,jl[i].jly)]=jl[i].id;
}
sort(jl+1,jl+1+n,cmplh);
for(int i=1;i<=n;i++){
if(jl[i].jlb!=1) break;
int ks=jl[i].id;
while(jl[i].jlx==jl[i+1].jlx && jl[i+1].jlb==1){
i++;
}
htm[jl[i].jlx]=jl[i].id;
}
sort(jl+1,jl+1+n,cmpll);
for(int i=1;i<=n;i++){
if(jl[i].jlb!=2) break;
int ks=jl[i].id;
while(jl[i].jly==jl[i+1].jly && jl[i+1].jlb==2){
i++;
}
ztm[jl[i].jly]=jl[i].id;
}
sort(jl+1,jl+1+n,cmpry);
for(int i=1;i<=n;i++){
if(jl[i].jlb!=3) break;
int nx=jl[i].jlx,ny=jl[i].jly;
for(int j=0;j<8;j++){
int mx=nx+dx[j];
int my=ny+dy[j];
if(mpp[make_pair(mx,my)]){
}
}
}
for(int i=1;i<=n;i++){
if(jl[i].jlb==1) continue;
int ks=jl[i].id;
}
for(int i=1;i<=n;i++){
if(jl[i].jlb==2) continue;
int ks=jl[i].id;
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tar(i);
}
for(int i=1;i<=n;i++){
int u=b[j].to;
if(shuyu[i]!=shuyu[u] && mp[make_pair(shuyu[i],shuyu[u])]==0){
rd[shuyu[u]]++;
mp[make_pair(shuyu[i],shuyu[u])]=1;
}
}
}
for(int i=1;i<=js;i++){
if(rd[i]==0){
rd[i]++;
}
}
tp();
for(int i=1;i<=js;i++){
ans=max(ans,f[i]);
}
printf("%dn",ans);
return 0;
}```