bzoj 2959 长跑 题解

Description

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

Solution

开2个并查集,一个保存的是原树之间的关系用来判断连通性,一个保存的是强联通分量的代表节点。

每连一条边u-v,就用第一个并查集判断一下u,v是否连通。如果没有,就直接连接,否则意味着图中出现了一个环。我们把这个环上的所有节点(也就是原来u-v的路径上的所有点)的点权移到一个代表节点上,然后丢掉其他所有点,还要把所有点的第二个并查集的父亲赋值为代表节点,因为它们属于的强联同分量改变了。

对于舍弃掉的点,只要保证不会在各种操作的时候跳到即可。具体实现时,只要把所有的fa改为getfa(fa)即可,就会跳到代表节点上。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,op,x,y,a[150010];
namespace IO{
	inline int read(){int res=0,f=1;char ch=getchar();while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch&15),ch=getchar();return res*f;}
	inline void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x+'0');else write(x/10),putchar(x%10+'0');}
}
namespace UFS{
	int fa[150010][2];
	inline int getfa(int x,int y){return fa[x][y]==x?x:fa[x][y]=getfa(fa[x][y],y);}
	inline void merge(int x,int y,int z){if(x=getfa(x,z),y=getfa(y,z),x!=y) fa[x][z]=y;}
}
namespace LCT{
	struct node{int s,v,ch[2],fa,tag;}tr[150010];
	int stk[150010],top;
	inline bool isroot(int x){return tr[UFS::getfa(tr[x].fa,1)].ch[0]!=x&&tr[UFS::getfa(tr[x].fa,1)].ch[1]!=x;}
	inline void pushup(int x){tr[x].s=tr[x].v+tr[tr[x].ch[0]].s+tr[tr[x].ch[1]].s;}
	inline void flip(int x){swap(tr[x].ch[0],tr[x].ch[1]);tr[x].tag^=1;}
	inline void pushdown(int x){
		if(!tr[x].tag) return ;
		if(tr[x].ch[0]) flip(tr[x].ch[0]);
		if(tr[x].ch[1]) flip(tr[x].ch[1]);
		tr[x].tag=0;
	}
	inline void rotate(int x){
		int y=UFS::getfa(tr[x].fa,1),z=UFS::getfa(tr[y].fa,1),k=tr[y].ch[1]==x,v=tr[x].ch[!k];
		if(!isroot(y)) tr[z].ch[tr[z].ch[1]==y]=x;
		tr[x].ch[!k]=y,tr[y].ch[k]=v;
		if(v) tr[v].fa=y;
		tr[y].fa=x,tr[x].fa=z;
		pushup(y),pushup(x);
	}
	inline void splay(int x){
		int y=x,z;top=0;stk[++top]=y;
		while(!isroot(y)) stk[++top]=y=tr[y].fa;
		while(top) pushdown(stk[top--]);
		while(!isroot(x)){
			y=UFS::getfa(tr[x].fa,1),z=UFS::getfa(tr[y].fa,1);
			if(!isroot(y)) rotate((tr[y].ch[0]==x)^(tr[z].ch[0]==y)?x:y);
			rotate(x);
		}
		pushup(x);
	}
	inline void access(int x){for(int y=0;x;x=UFS::getfa(tr[y=x].fa,1)) splay(x),tr[x].ch[1]=y,pushup(x);}
	inline void makeroot(int x){access(x),splay(x),flip(x);}
	inline int findroot(int x){access(x),splay(x);while(tr[x].ch[0]) pushdown(x),x=tr[x].ch[0];return x;}
	inline void split(int x,int y){makeroot(x),access(y),splay(y);}
	inline void link(int x,int y){makeroot(x);tr[x].fa=y;}
	inline void cut(int x,int y){split(x,y);if(findroot(y)==x&&tr[x].fa==y&&!tr[x].ch[1]) tr[x].fa=tr[y].ch[0]=0,pushup(y);}
	inline void reset(int x){tr[x].fa=tr[x].ch[0]=tr[x].ch[1]=0,pushup(x);}
	inline void change(int x,int y){int t=UFS::getfa(x,1);splay(t),tr[t].v-=a[x],a[x]=y,tr[t].v+=a[x],pushup(x);}
}
inline int dfs(int f,int x){
	if(!x) return 0;
	UFS::fa[x][1]=f;
	return dfs(f,LCT::tr[x].ch[0])+dfs(f,LCT::tr[x].ch[1])+LCT::tr[x].v;
}
int main(){
	n=IO::read(),m=IO::read();
	for(int i=1;i<=n;i++) UFS::fa[i][0]=UFS::fa[i][1]=i,LCT::tr[i].s=LCT::tr[i].v=a[i]=IO::read();
	for(int i=1;i<=m;i++){
		op=IO::read(),x=IO::read(),y=IO::read();
		if(op==1){
			if(x=UFS::getfa(x,1),y=UFS::getfa(y,1),x==y) continue ;
			if(UFS::getfa(x,0)!=UFS::getfa(y,0)) LCT::link(x,y),UFS::merge(x,y,0);
			else LCT::split(x,y),LCT::tr[x].v=dfs(x,y),LCT::reset(x);
		}else if(op==2) LCT::change(x,y);
		else if(op==3){
			if(UFS::getfa(x,0)!=UFS::getfa(y,0)){puts("-1");continue ;}
			x=UFS::getfa(x,1),y=UFS::getfa(y,1),LCT::split(x,y),IO::write(LCT::tr[y].s),putchar('\n');
		}
	}
} 
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇