首页 > 代码库 > BZOJ 1924 所驼门王的宝藏(强连通分量+树形DP)

BZOJ 1924 所驼门王的宝藏(强连通分量+树形DP)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1924

题意:


思路:首先建立所有可达点之间的有向图。之后求强连通分量SCC,缩点重新构图。然后就是一个树,树形DP一下即可。

 

int n,r,c;map<i64,int> mp;map<int,int> mp1,mp2;struct node{    int x,y,op;};node a[N];int visit[N];vector<int> V1[N],V2[N];int X,Y;void Add(int x,int y,int i){    if(mp1.count(x)==0) mp1[x]=++X;    V1[mp1[x]].pb(i);        if(mp2.count(y)==0) mp2[y]=++Y;    V2[mp2[y]].pb(i);}int dx[]={-1,-1,-1,0,1,1,1,0};int dy[]={-1,0,1,1,1,0,-1,-1};vector<int> g[N];void build(){    int i,j,k,p,x,y;    i64 q;    FOR1(i,n)    {        if(a[i].op==1)        {            p=mp1[a[i].x];            FOR0(j,SZ(V1[p])) if(V1[p][j]!=i) g[i].pb(V1[p][j]);         }        else if(a[i].op==2)        {            p=mp2[a[i].y];            FOR0(j,SZ(V2[p])) if(V2[p][j]!=i) g[i].pb(V2[p][j]);        }        else        {            FOR0(j,8)            {                x=a[i].x+dx[j];                y=a[i].y+dy[j];                if(x<1||x>r||y<1||y>c) continue;                q=x*M+y;                if(mp.count(q)) g[i].pb(mp[q]);            }        }    }}int dfn[N],low[N],color[N],id,num,size[N];stack<int> St;void DFS(int u){    dfn[u]=low[u]=++id;    St.push(u);        int i,v;    FOR0(i,SZ(g[u]))    {        v=g[u][i];        if(!dfn[v]) DFS(v),upMin(low[u],low[v]);        else if(!visit[v]) upMin(low[u],dfn[v]);    }    if(low[u]==dfn[u])    {        num++;        do        {            v=St.top();            St.pop();            visit[v]=1;            color[v]=num;            size[num]++;        }while(u!=v);    }}vector<int> G[N];int d[N];int rebuild(){    int i,j;    FOR1(i,n) FOR0(j,SZ(g[i]))    {        if(color[i]!=color[g[i][j]])        {            G[color[i]].pb(color[g[i][j]]);            d[color[g[i][j]]]++;        }    } }int f[N];int dfs(int u){    if(f[u]!=-1) return f[u];    f[u]=0;    int i,v;    FOR0(i,SZ(G[u])) upMax(f[u],dfs(G[u][i]));    f[u]+=size[u];    return f[u];}int main(){    RD(n,r,c);    int i;    i64 p;    FOR1(i,n)    {        RD(a[i].x,a[i].y,a[i].op);        Add(a[i].x,a[i].y,i);        p=a[i].x*M+a[i].y;        mp[p]=i;    }    build();    FOR1(i,n) if(!visit[i]) DFS(i);    rebuild();clr(f,-1);    int ans=0;    FOR1(i,num) if(!d[i]) upMax(ans,dfs(i));    PR(ans);}