[bzoj1924] 所驼门王的宝藏-白红宇

[bzoj1924] 所驼门王的宝藏

阅读量：6815 次

发布时间：2019-06-26

本文共 2335 字，大约阅读时间需要 7 分钟。

题意：给你一个网格图，再给你n个点，每个点有一个传送门，可以传送到别的点，传送门有三种，横向，纵向，九宫格，你一开始可以任选一个点为起点，问你最多能经过多少个点。

题解：

tarjan+拓扑排序+dag上的dp

首先这题数据比较水，行和列都是\(10^5\)级别的

将能互相到达的点连边，tarjan缩点后变成dag

考虑在dag上dp，但是要满足拓扑序，所以对缩点后的图进行拓扑排序

然后直接简单dp即可

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #define ll long long#define N 100010using namespace std;int n,r,c,e_num,e_num2,top,cnt,tot,ans,dep;int vx[N],vy[N],vt[N],nxt[N*50],to[N*50],h[N],nxt2[N*50],to2[N*50],h2[N];int dfn[N],low[N],stk[N],bl[N],num[N],inx[N],dp[N];int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};vector
            
              v1[N],v2[N];map
             
              
               ,int> mp;int gi() { int x=0,o=1; char ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}void add(int x, int y) { nxt[++e_num]=h[x],to[e_num]=y,h[x]=e_num;}void add2(int x, int y) { nxt2[++e_num2]=h2[x],to2[e_num2]=y,h2[x]=e_num2;}void tarjan(int u) { dfn[u]=low[u]=++dep; stk[++top]=u; for(int i=h[u]; i; i=nxt[i]) { int v=to[i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(!bl[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { cnt++; while(1) { int v=stk[top--]; bl[v]=cnt,num[cnt]++; if(u==v) break; } }}void toposort() { for(int i=1; i<=cnt; i++) { if(!inx[i]) { stk[++top]=i,dfn[++tot]=i; dp[i]=num[i]; } } while(top) { int u=stk[top--]; for(int i=h2[u]; i; i=nxt2[i]) { int v=to2[i]; inx[v]--; if(!inx[v]) stk[++top]=v,dfn[++tot]=v; } }}int main() { n=gi(),r=gi(),c=gi(); for(int i=1; i<=n; i++) { vx[i]=gi(),vy[i]=gi(),vt[i]=gi(); v1[vx[i]].push_back(i); v2[vy[i]].push_back(i); mp[make_pair(vx[i],vy[i])]=i; }//O(n*logn) for(int i=1; i<=n; i++) { if(vt[i]==1) { int sz=v1[vx[i]].size(); for(int j=0; j
               
                 pa=make_pair(vx[i]+dx[j],vy[i]+dy[j]); if(mp[pa]) add(i,mp[pa]); } } }//期望O(n)? for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i); for(int u=1; u<=n; u++) for(int i=h[u]; i; i=nxt[i]) { int v=to[i]; if(bl[u]!=bl[v]) inx[bl[v]]++,add2(bl[u],bl[v]); } toposort(); for(int j=1; j<=cnt; j++) { int u=dfn[j]; for(int i=h2[u]; i; i=nxt2[i]) { int v=to2[i]; dp[v]=max(dp[v],dp[u]+num[v]); } } for(int i=1; i<=cnt; i++) ans=max(ans,dp[i]); printf("%d\n", ans); return 0;}