BZOJ 1924 [Sdoi2010]所驼门王的宝藏 tarjan缩点+拓扑DP

题意: 一个r*c的图中，有n个宫殿。 每个宫殿有一个类型。 类型1:可以到达他所在的行的任意宫殿。 类型2:可以到达他所在的列的任意宫殿。 类型3:可以到达他四周八个格子的任意宫殿。 现在你从任意一个宫殿开始，询问你最多访问多少个宫殿。 解析: 填坑计划。 这题建边好麻烦=-= 首先先建出来从哪个宫殿可以到哪个宫殿的图。 之后我们发现对于一个强连通分量来说，如果访问了一个点，那么即可以访问该强连通分量中的所有点。 所以我们可以tarjan缩一下点，，然后重新建图。 然后我们发现重新建出来的图是个DAG。 (不知道当年哪个2b说是一棵树？) 所以我们可以在这个DAG上拓扑DP，f[i]表示从某点出发到i最多走多少点权和(点的点权为强连通分量中的原来的点的个数)。 代码:

;ll;ll n,r,c;int xx[]={0,1,0,-1,-1,-1,0,1,1};int yy[]={0,1,1,1,0,-1,-1,-1,0};int head[N],head2[N],head3[N],head4[N];int cnt,cnt2,cnt3,cnt4;struct node{int to,next;}linkx[N*10],linky[N*10],newedge[N*10];struct node2{int from,to,next;}edge[N*40];struct Point{int x,y,type;Point(){}Point(int _x,int _y):x(_x),y(_y){}friend istream& operator >> (istream &_, Point &a){scanf(“%d%d%d”,&a.x,&a.y,&a.type);return _;}< (Point a,Point b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}}pt[N];map<ll,int>ma;map<Point,int>ma2;void init(){memset(head2,-1,sizeof(head2));memset(head,-1,sizeof(head));cnt=1,cnt2=1;}void init2(){memset(head3,-1,sizeof(head3));cnt3=1;}void init3(){memset(head4,-1,sizeof(head4));cnt4=1;}void edgeadd(int from,int to,int *head,node *edge,int &cnt){edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}void edgeadd2(int from,int to,int *head,node2 *edge,int &cnt){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}bool ins[N];int deep[N],low[N],sta[N],top,tot;int belong[N],num[N],cnt_block;void tarjan(int now,int ff){deep[now]=low[now]=++tot;sta[++top]=now,ins[now]=1;for(int i=head3[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(!deep[to]){tarjan(to,now);low[now]=min(low[now],low[to]);}else if(ins[to])low[now]=min(low[now],deep[to]);}if(deep[now]==low[now]){cnt_block++;int t=-1;do{t=sta[top–];ins[t]=0;belong[t]=cnt_block;num[cnt_block]++;}while(t!=now);}}int in[N];int f[N];void topsort(){queue<int>q;memset(f,-0x3f,sizeof(f));for(int i=1;i<=cnt_block;i++)if(!in[i])q.push(i),f[i]=num[i];while(!q.empty()){int u=q.front();q.pop();for(int i=head4[u];i!=-1;i=newedge[i].next){int to=newedge[i].to;f[to]=max(f[to],f[u]+num[to]);in[to]–;if(in[to]==0)q.push(to);}}}int main(){#ifndef ONLINE_JUDGEfreopen(“sotomon8.in”,”r”,stdin);freopen(“test.out”,”w”,stdout);#endifinit(),init2();scanf(“%lld%lld%lld”,&n,&r,&c);for(int i=1;i<=n;i++){cin>>pt[i],ma[(ll)(pt[i].x-1)*c+pt[i].y]=i;edgeadd(pt[i].x,i,head,linkx,cnt);edgeadd(pt[i].y,i,head2,linky,cnt2);}for(int i=1;i<=n;i++){if(pt[i].type==1){for(int j=head[pt[i].x];j!=-1;j=linkx[j].next){int to=linkx[j].to;if(to==i)continue;edgeadd2(i,to,head3,edge,cnt3);}}else if(pt[i].type==2){for(int j=head2[pt[i].y];j!=-1;j=linky[j].next){int to=linky[j].to;if(to==i)continue;edgeadd2(i,to,head3,edge,cnt3);}}else{for(int j=1;j<=8;j++){ll tmpx=pt[i].x+xx[j],tmpy=pt[i].y+yy[j];int no=ma[(ll)(tmpx-1)*c+tmpy];if(no!=0)edgeadd2(i,no,head3,edge,cnt3);}}}for(int i=1;i<=n;i++)if(!deep[i])tarjan(i,0);init3();for(int i=1;i<cnt3;i++){int x=edge[i].from,y=edge[i].to;if(belong[x]!=belong[y]&&!ma2[Point(belong[x],belong[y])])ma2[Point(belong[x],belong[y])]=1,edgeadd(belong[x],belong[y],head4,newedge,cnt4),in[belong[y]]++;}topsort();int ans=0;for(int i=1;i<=cnt_block;i++)ans=max(ans,f[i]);printf(“%d\n”,ans);#ifndef ONLINE_JUDGEfclose(stdin);fclose(stdout);;}

可是我要如何在浅薄的纸上为你画上我所有的命轮？