bzoj3959(LCT)

题目描述

某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”，同学们纷纷离开寝室，离开教室，离开实验室，到操场参加3000米长跑运动。一时间操场上熙熙攘攘，摩肩接踵，盛况空前。
　　为了让同学们更好地监督自己，学校推行了刷卡机制。
　　学校中有n个地点，用1到n的整数表示，每个地点设有若干个刷卡机。
　　有以下三类事件：
　　1、修建了一条连接A地点和B地点的跑道。
　　2、A点的刷卡机台数变为了B。
　　3、进行了一次长跑。问一个同学从A出发，最后到达B最多可以刷卡多少次。具体的要求如下：
　　当同学到达一个地点时，他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次，即使多次到达同一地点也不能多次刷卡。
　　为了安全起见，每条跑道都需要设定一个方向，这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向，按照任意路径从A地点到B地点能刷卡的最多次数。

题解

我们可以想一下题目说的一条合法路径指的是什么，从一个点到另一个点，中间的路和环都可以走。

所以有一个想法，如果图是静态的，我们可以先边双缩点，然后倍增一下就好了。

但这个图是动态的。所以我们用一个LCT来维护这个过程。

如果我们有一条边连接的两个点原来就是联通的，我们可以把这条链缩成一个点，怎么缩呢，先把链拿出来，然后把这条链上的所有点都指向splay的顶端，然后把顶端的点和其他的点断开，然后这个LCT中只有某些点的father是不对的，所以在访问father的时候要find一下。

注意每次遍历时都要pushdown

代码

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define ls tr[x][0] #define rs tr[x][1] #define father find(fa[x]) #define N 150009 using namespace std; int bcj[N],f[N],tr[N][2],fa[N],size[N],val[N],n,m,v[N]; bool rev[N]; inline int rd(){int x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } int find(int x){return f[x]=f[x]==x?x:find(f[x]);} int fd(int x){return bcj[x]=bcj[x]==x?x:fd(bcj[x]);} inline bool ge(int x){return tr[father][1]==x;} inline bool isroot(int x){return tr[father][1]!=x&&tr[father][0]!=x;} inline void pushup(int x){size[x]=size[ls]+size[rs]+val[x];} inline void pushdown(int x){if(rev[x]){rev[ls]^=1;rev[rs]^=1;rev[x]^=1;swap(ls,rs);}} inline void _pushdown(int x){if(!isroot(x))_pushdown(father);pushdown(x);} inline void rotate(int x){int y=father,o=ge(x);tr[y][o]=tr[x][o^1];fa[tr[y][o]]=y;if(!isroot(y))tr[find(fa[y])][ge(y)]=x;fa[x]=fa[y];//!!!!fa[y]=x;tr[x][o^1]=y;pushup(y);pushup(x); } inline void splay(int x){_pushdown(x);while(!isroot(x)){int y=father;if(isroot(y))rotate(x);else rotate(ge(y)==ge(x)?y:x),rotate(x);} } inline void access(int x){for(int y=0;x;y=x,x=father)splay(x),tr[x][1]=y,pushup(x);} inline void makeroot(int x){access(x);splay(x);rev[x]^=1;} inline void split(int x,int y){makeroot(x);access(y);splay(y);} inline void link(int x,int y){makeroot(x);fa[x]=y;} void dfs(int x,int rt){f[x]=rt;pushdown(x);////!!!!!!if(ls)dfs(ls,rt);if(rs)dfs(rs,rt); } int main(){n=rd();m=rd();int opt,x,y;for(int i=1;i<=n;++i)f[i]=i,v[i]=val[i]=rd(),bcj[i]=i;for(int i=1;i<=m;++i){opt=rd();x=rd();y=rd();if(opt==1){x=find(x);y=find(y);if(x==y)continue;int tx=fd(x),ty=fd(y);if(tx!=ty){bcj[tx]=ty;link(x,y);}else{split(x,y);dfs(y,y);val[y]+=size[tr[y][0]];tr[y][0]=0;pushup(y);}}else if(opt==2){int cha=y-v[x];v[x]=y;x=find(x);access(x);splay(x);val[x]+=cha;pushup(x);}else{x=find(x);y=find(y);if(fd(x)!=fd(y)){printf("-1\n");continue;}split(x,y);printf("%d\n",size[y]);}}return 0; }

 

转载于:https://www.cnblogs.com/ZH-comld/p/10206802.html

总结

以上是生活随笔为你收集整理的bzoj3959(LCT)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。