首页 > 代码库 > 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);}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。